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
ĐẠ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ựphat triên maṇ h me cua ha ̣tầng Internet đa cho ra đơi
̀
́
̃
̉
̃
̀
̉
nhưng ưng duṇ g mơi thay đôi hoan toan cach tương tac của con người vơi nhau trên
̃
́
́
̀
̀
́
́
́
toàn thế giới. Kết nối vơi baṇ be thông qua maṇ g Internet trơ nên đơn gian hơn bao giơ
̉
̉
́
̀
̀
hết nhơ nhưng ưng duṇ g nh ư Chat , Voice Call , Video Conference..Hay như cach
̀
̃
́
́
thưc xem truyền hinh IP TV, xem video theo yêu cầu thông qua maṇ g Internet vơi chất
́
́
̀
lươṇ g cao cung 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 nay đượ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 khoa luâṇ .
́
Truyền tin multicast thơi gian thưc̣ trên maṇ g ngang hang la môṭ nhanh 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ô hinh maṇ g ngang hang co nhưng đăc̣ trưng riêng biêṭ . Vơi
̀
́
̃
́
̀
̉
mô hinh maṇ g ngang hang ngươi thiết kế co thê tâṇ duṇ g băng thông va kha năng lưu
̉
̀
̀
́
̀
̀
trư cua cac may tham gia maṇ g 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 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 hang ngày càng nhiều khi ma cac nghiên cưu trên mô hinh 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 đap ư ng đươc̣
́
́ ́
các yêu cầu đăc trưư g như đam bao độtrễtaị cac node tham gia maṇ g 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.2. Multicast tầng ứng dụng .................................................................................6
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
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
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.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
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 phat triên vơi tốc độchong măṭ . Tốc độ
̀
́
́
́
truyền tai trên maṇ g cao đa lam 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 lam thay đôi cach
̀
̀
́
giao tiếp cua con ngươi , thu hep̣ moị khoang cach vâṭ li , mang đến cho chung ta
̉
̉
̀
́
́
́
nhưng trai nghiêṃ mơi me về cuôc̣ sống.
̃
̉
́
̉
Truyền tin multicast co 2 loại chꢁnh là IP multicast và multicast trên tầng ứng
́
̉
dụng. IP Multicast co thê xem la phương phap multicast chinh thống , hiêụ qua nhất .
̉
́
̀
́
́
̉
Tuy nhiên khi triên khai trên maṇ g Internet thi IP Multicast găp̣ nhưng trơ ngaị rất
̃
̉
̀
lơn : đo la chi phi cho viêc̣ thay thế router trên toan maṇ g Inter net (do cac router trươc
́
́ ̀
̀
́
́
́
đây không co kha 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 vi 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 cung găp̣
́
̃
không it vấn đề . Thay vi nhân ban cac goi tin taị cac router như IP Multicast , cơ chế
̉
́
́
́
́
̀
Multicast trên tầng ưng duṇ g laị nhân ban cac goi tin trên cac ma y đầu cuối . Do đo
̉
́
́
́
́
́
́
viêc̣ tối ưu cây multicast nhằm taọ sựcân bằng tai tương đối trên toan maṇ g cung la
̉
̃
̀
̀
môṭ vấn đề . Môṭ vấn đề nưa phai tinh đến la độtrễ . Các gói tin liên tục phải luân
̃
̉
̀
́
̉
̃
chuyên qua nhiều vi ṭ ri đầu cuối nên độtrê se tăng cao . Viêc̣ xây dưṇ g đươc̣ môṭ cây
̃
́
̉
̉
̃
multicast phu hơp̣ đê giam thiêu độtrê cung la môṭ vấn đề quan troṇ g.
̉
̃
̀
̀
Hiêṇ nay đa co nhưng nghiên cưu xây dưṇ g cây multicast đa luồng trên maṇ g
̃ ́
̃
́
ngang hang co cấu truc như Sp litstream. Splitstream đươc̣ xây dưṇ g dưạ trên nền tang
̉
̀
́
́
̉
Pastry, Scribe thêm vao đo môṭ số giai phap đê haṇ chế tinh traṇ g qua tai taị môṭ số
̉
̉
̀
́
́
́
̀
node tham gia maṇ g. Nghiên cưu nay đã 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 đꢁ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 goi tin đến tất ca cac node khac ma no biết , trong khi nhưng node thưc̣ sựcần dư
̉
̉
̃
̃
́
́
́
̀ ́
liêụ không phai la tất ca cac node ấy . Điều nay thưc̣ sựlam lang phi băng thông cua
̉
̉
̃
̉
̀
́
̀
̀
́
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 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.
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 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̣ cac vấn đề kho khăn :
́
́
̉
Khi triên khai trên hê ̣thống lơn như Internet cac router phai lưu giư rất nhiều
̉
̃
́
́
trạng thái của các nhóm . Đây thưc̣ sựla môṭ vấn đề lơn khi số nhom tăng lên
̀
́
́
cao.
Tạo và duy trì một cây multicast mất rất nhiều tai 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.
̉
́
̉
Vấn đề lơn nhất cua viêc̣ triên khai IP Multicast la 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.
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
phꢁa dưới. Độ mạnh yếu của các giao thức tầng ứng dụng được đo bởi việc đo
đạc sꢀ mất mát dữ liệu truyền khi các thành viên bị lỗi và thời gian mà nó cần
để giao thức có thể khôi phục lại để truyền cho các thành viên khác.
Quá tꢀi : để sử dụng hiệu quả tài nguyên mạng, quá tải điều khiển ở mỗi thành
viên nên nhỏ. Đó là một thông số giá thành quan trọng để đo đạc tính mở rộng
của thành viên.
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 tꢁnh chất phân tán và không xác định được về
phương diện địa lý của các máy thật.
Dꢀa vào topology đó, các node tương ứng với các node trên cây multicast (node
lá hoặc node con), liên kết ảo sẽ tạo nên cơ chế truyền tin từ node lá sang các node con.
Có hai cách thức truyền thông multicast: multicast trên mạng có cấu trúc (tree-
first) và multicast trên mạng không có cấu trúc (mesh-first). Sau đây ta sẽ nghiên cứu
phân tích và lꢀa chọn một hướng truyền thông phù hợp cho video streaming.
Multicast theo hướng mesh-first
Trong cách tiếp cận mesh-first, các node trước khi tham gia vào cây phải là thành
viên của một mạng phủ nào đó, và giữa chúng đã tồn tại các liên kết với nhau dạng
lưới. Sau đó, cây multicast sẽ được xây dꢀng dꢀa trên các liên kết của mạng phủ này.
Giao thức Narada là một trong những giao thức multicast tầng ứng dụng đầu tiên
và theo hướng mesh-first. Nó chỉ định một máy đặc biệt là Rendezvous Point (RP)
được sử dụng để theo dõi sꢀ gia nhập của một thành viên mới.
Tất cả các giao thức multicast tầng mạng cũng sử dụng một hoặc một số các thꢀc
thể tương tꢀ như RP trong Narada để tạo cơ chế gia nhập.
Xây dựng mesh: khi một node mới muốn gia nhập nhóm multicast, nó sẽ có danh
sách thành viên đã gia nhập vào mesh do RP cung cấp. Sau đó thành viên mới sẽ lꢀa
chọn ngẫu nhiên một số các thành viên và gia nhập vào mesh và coi như là láng giềng
của những thành viên đó. Quy trình gia nhập thành công khi mà ít nhất một thành viên
trong danh sách đồng ý để thành viên mới là láng giềng mesh.
Khi gia nhập vào mesh, thành viên mới bắt đầu định kỳ trao đổi thông điệp với
các lang giềng mesh của nó. Bất cứ khi nào một node gia nhập hoặc một thành viên rời
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à kꢁch thước của nhóm. Do đó, giao thức Narada hiệu quả chỉ khi kꢁch thước
nhóm Multicast là nhỏ.
Hình 5. Giao thức Narada
Khi cả thành viên D và E cùng lỗi, mesh phân chia thành 2 phần. Do đó, các
thành viên A, B và C sẽ ngừng nhận được thông tin trạng thái từ F, G và H; và ngược
lại. Mỗi thành viên có thể khảo sát các thành viên từ khi nó ngừng nhận được thông
điệp trạng thái để tạo ra một kết nối mới và sửa các phần. Chý ý rằng, việc sửa không
yêu cầu sꢀ hỗ trợ của RP và do đó vẫn có thể thꢀc hiện được ngay cả khi RP bị lỗi.
Đường truyền dữ liệu: các thành viên của một nhóm thꢀc hiện một giao thức
định tuyến để tꢁnh ra các đường đi unicast trong mesh.
Sự chọn lọc của mesh: các đường truyền dữ liệu trong Narada là các cây nhịp
của mesh. Do đó, chất lượng của đường truyền dữ liệu phụ thuộc vào chất lượng của
các kết nối là một phần của mesh. Khi một thành viên mới tham gia, hoặc khôi phục từ
các phần, một tập ngẫu nhiên các cạnh sẽ được thêm vào mesh. Do đó, sꢀ chọn lọc
định kỳ cần phải được thꢀc hiện với các cạnh để cải tiến chất lượng của các đường
truyền dữ liệu. Việc thêm cạnh (J,G) là có ích bởi vì một số lượng lớn các node unicast
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 chꢁ như cân bằng băng thông giữa các
node hoặc đảm bảo độ sâu của cây cân bằng giữa các nhánh.
Ưu điểm của mô hình này là các node có thể chọn node cha, do đó có thể tránh
được tình trạng một node nào đó phải chịu tải quá cao.
Hình 6. Mạng phủ 7 node (a) và cây multicast xây tương ứng (b)
Scribe là hệ thống multicast tầng ứng dụng mở rộng được xây dꢀng trên Pastry.
Để tạo nhóm multicast, Scribe tạo ra một khoá Pastry tꢀ động được biết như Id của
một nhóm. Cây multicast tương ứng với một nhóm được thꢀc hiện bằng một tập hợp
các bộ định tuyến Pastry từ một node thành viên đến nhóm gốc của Id. Bằng việc
truyền lùi lại trên đường dẫn, các gói tin multicast từ gốc tới mỗi thành viên.
SplitStream là hướng phát triển sau của Scribe mà tập trung vào việc phân bổ truyền
thông.
Ngoài Scribe là hệ thống multicast tầng ứng dụng xây dꢀng trên Pastry, ta cũng
có thể xây dꢀng multicast trên các mạng ngang hàng có cấu trúc DHT khác như CAN,
CHORD…
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 tꢁnh để duy trì mạng ngang hàng được
giảm xuống mức tối thiểu. Băng thông của mạng được dành nhiều hơn cho việc chia sẻ
tài nguyên.
Tuy nhiên nhược điểm của mô hình này là khi một node nào đó bị lỗi, việc khôi
phục lại cây multicast để đảm bảo luồng dữ liệu cho các node con là tương đối khó
khăn do mỗi node biết rất ít thông tin về các node khác trong mạng.
1.2.Truyền tin multicast thời gian thực
Một nhánh trong truyền tin multicast là truyền tin multicast thời gian thꢀc.
Phương pháp truyền tin này thường được áp dụng trong các ứng dụng video streaming
trꢀc tiếp có thể xem là thế mạnh thꢀc sꢀ của mạng ngang hàng so với mô hình mạng
client – server truyền thống. Ví dụ cụ thể nhất là khi chúng ta muốn xem một trận đá
bóng rất được mong đợi giữa Real Maldrid – Barcelona. Một thống kê cho biết có đến
gần 1 tỷ người theo dõi trận cầu này trên toàn thế giới và chắc chắn là tại thời điểm đó
không có 1 server nào có thể đủ mạnh để phát sóng trꢀc tiếp trận đấu lên mạng
Internet. Thế nhưng với 1 ứng dụng của video streaming thời gian thꢀc trên mạng
ngang hàng (như Sopcast , TVU Player) bạn lại có thể theo dõi trận đấu này với chất
11
lượng có thể chấp nhận được. Đó chꢁnh là ưu điểm vượt trội của mô hình mạng ngang
hàng và hiện nay vẫn đang được phát triển để ngày càng tối ưu hóa. Khóa luận này
cũng là một đề xuất về truyền tin multicast đa luồng thời gian thꢀc dꢀa trên giao thức
Chord nhằm ứng dụng cho video streaming thời gian thꢀc.
Trong truyền tin multicast thời gian thꢀc có 2 đặc tính riêng quan trọng nhất cần
phải đáp ứng để đạt được chất lượng có thể chấp nhận được :
Inbound bandwith tại mỗi máy là đủ lớn để decode được thành video với chất
lượng chấp nhận được . Với các kỹ thuật decode bây giờ thì các máy với mức
download lớn hơn 240Kbits/s là có thể xem được video.
Độ trễ tại các máy là không quá lớn để đảm bảo tính thời gian thꢀc . Tính chất
này thường rất quan trọng trong các ứng dụng video streaming 2 chiều như
video call … tuy nhiên trong các ứng dụng 1 chiều như các ứng dụng xem TV
trên Internet đặc tính này lại có thể không quá quan trọng
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 đꢁch lớn nhất cuả truyền tin multicast đa luồng là giải quyết được vấn đề
vừa đặt ra : làm sao đạt được tính công bằng cho các node tham gia hệ thống multicast.
Xét ví dụ ở Hình 7. Bây giờ ta quan tâm đến cả 2 luồng stripe 1 , 2. Sau khi xét
quá trình truyền tin của cả 2 luồng ta có thể thấy tất cả các node trong cây đều nhận 2
2 luồng dữ liệu và gửi đi 2 luồng dữ liệu. Nếu stripe 1 và stripe 2 là tương đương nhau
thì quả thꢀc hệ thống này đã đạt được sꢀ công bằng mong muốn.
Ví dụ ở Hình 7 có thể xem là hình mẫu đơn giản nhất cho cây multicast đa luồng.
Việc phát triển và ứng dụng trong hệ thống mạng ngang hàng với độ phức tạp lớn hơn
nhiều đã gặp 1 số vấn đề :
Số luồng mong muốn là lớn để đảm bảo mỗi luồng dữ liệu khi truyền đi trên
mạng đủ nhỏ để tránh tắc nghẽn. Việc tăng số luồng đồng nghĩa với cách xây
dꢀng việc gửi và nhân các luồng tại mỗi node trong cây multicast cũng sẽ phức
tạp hơn để đảm bảo vẫn giữ được tính công bằng
Tính không ổn định của mạng. Đây chꢁnh là đặc trưng thꢀc tế của hệ thống
mạng ngang hàng. Các node trong cây multicast sẽ vào ra liên tục và để cây
multicast vẫn đảm bảo truyền tin được đến tất cả các node thì cần phải có cơ
chế thay đổi lại cây multicast cho phù hợp.
Gần đây đã có một số nghiên cứu liên quan đến xây dꢀng cây multicast đa luồng
trên mạng ngang hàng có cấu trúc sử dụng giao thức DHT(Bảng băm phân tán -
Distributed Hash Table). Mục 2.2 sẽ trình bày về những giải pháp này
2.2.Splitstream
Splitstream là giải pháp xây dꢀng cây multicast đa luồng dꢀa trên nền tảng
Pastry , Scribe.
Để hiểu được Splitstream ta sẽ tìm hiểu rõ về cấu trúc Pastry và Scribe ngay sau
đây.
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
Ở Hình 8 là bảng định tuyến của nodeId 10233102. Dꢀa vào bảng định tuyến này
node 10233102 có thể gửi dữ liệu đến cho node khác. Ví dụ node 10233102 muốn gửi
thông điệp m đến cho node 33321220. Đầu tiên nó sẽ tìm trong các node hàng xóm
trong bảng định tuyến , nếu có sẽ gửi đến luôn. Nếu không tìm thấy nó sẽ tìm trong
Routing table và so sánh các ký tꢀ ban đầu của node cần gửi đến (33321220) với các
cột trong Routing table. Cụ thể là node 33321220 có ký tꢀ đầu là 3 : nó sẽ tìm trong
Routing table tại hàng 1 cột 3 tìm được node 31203203. Do ngay từ ký tꢀ đầu của
node cần gửi đã khác node gửi nên quá trình tìm kiếm dừng lại. Node 10233102 sẽ gửi
đến node 31203203 với yêu cầu sẽ gửi thông điệp m đến node 33321220. Quá trình
này tiếp tục xảy ra cho đến khi đến được node cần gửi.
Hình 9. Node 10233102 gửi thông điệp m đến node 33321220
Các node định kỳ gửi các gói tin keep-alive cho các node hàng xóm của nó và
nếu như một node nào đó không nhận được gói keep-alive của một node hàng xóm
trong tập hàng xóm của nó trong một thời gian nhất định thì nó sẽ xem như node hàng
xóm đã rời khỏi mạng và tꢀ động update thông tin.
Scribe
Scribe là cơ sở hạ tầng cho việc truyền multicast ở tầng ứng dụng dꢀa trên giao
thức Pastry. Cũng chꢁnh vì thế nó thừa hưởng được những đặc tính của một giao thức
mạng ngang hàng có cấu trúc và đồng thời mang những đặc điểm này vào trong việc
16
truyền thông điệp multicast ở tầng ứng dụng. Giống như Pastry, Scribe là mô hình
phân quyền hoàn toàn nó có khả năng xây dꢀng, duy trình mạng, phát tán thông báo
một cách có tổ chức và tin cậy đồng thời có tꢁnh tương thꢁch cao với số lượng nhóm,
số thành viên trong nhóm lớn cũng như khi có nhiều tài nguyên trên mạng.
Scribe sẽ xây dꢀng một cây multicast bằng cách gọi thủ tục join giao thức Pastry
mỗi khi một nút có yêu cầu đăng nhập vào nhóm truyền multicast. Và nhờ khả năng tꢀ
cấu hình của Pastry mà vấn đề quản lý nút, nút lỗi cũng như ra vào của nút trở nên dễ
dàng. Đồng thời Scribe sử dụng giao thức Pastry để phát tán thông báo multicast.
Scribe tổ chức theo nhóm, tức là hợp những node có cùng nhu cầu nhận dữ liệu
multicast vào một nhóm, và về mặt logic thì các node trong nhóm sẽ có quan hệ với
nhau theo hình cây(sẽ giải thích kỹ ở phần sau). Bất kỳ một node nào trong mạng cũng
có thể thꢀc hiện được 3 thao tác: một là tạo ra 1 group, hai là join vào một group đã có
từ trước (trở thành một node trong cây multicast) và ba là truyền multicast tới tất cả
các node có trong group (nguồn multicast). Scribe là một mô hình cung cấp một cách
cố gắng tối đa trong việc truyền multicast nó có thể quản lý và duy trì được nhiều
group cùng một lúc, các group có số lượng thành viên lớn cũng như có nhiều tài
nguyên trong mạng.
Chi tiết giải thuật:
Mô hình:
Mô hình để thꢀc thi Scribe là một mạng Pastry trong đó các máy có cài đặt
chương trình ứng dụng của Scrible. Chương trình ứng dụng này sẽ cung cấp cho các
máy này hai phương thức là forward (được gọi khi một thông điệp định tuyến qua một
node) và deliver (được gọi khi thông điệp đến một node mà có nodeId gần với key
nhất hoặc nội dung thông điệp chꢁnh là địa chỉ của node đó). Các thông điệp trong
Scribe có 4 kiểu là : JOIN (xin tham gia vào một group), CREATE (tạo một group
mới), LEAVE (rời khỏi group), MULTICAST (truyền thông điệp multicast).
Quản lý nhóm:
–Mỗi nhóm truyền multicast có một định danh groupId duy nhất
Scirbe node (tức là node trong mạng có cài chương trình ứng dụng Scrible) có
id gần với id của group (groupId) nhất được gọi là “điểm gặp” và nó cũng chꢁnh
là gốc của cây multicast tương ứng với groupId này luôn.
–Tạo Nhóm: Một node Scribe nào đó muốn khởi tạo một group thì các bước thꢀc
hiện sẽ là :
17
B1: node Scribe dùng Pastry định tuyến thông điệp route(CREATE,groupId).
B2: giao thức Pastry sẽ gửi thông điệp này tới điểm cuối là một node có nodeId
gần với groupId nhất. Và node này sẽ được xem như là gốc của group mới tạo
ra.
B3: Hệ thống sẽ kiểm tra độ an toàn, các thông tin về chứng thꢀc nếu không có
vấn đề gì thì sẽ thêm group mới vào danh sách các group đã biết trong mạng.
Trong việc tạo nhóm bước quan trọng nhất chꢁnh là bước kiểm tra độ an toàn và
chứng thꢀc thông tin, vì điều này có ảnh hưởng rất lớn tới sꢀ an toàn của toàn mạng
nói chung chứ không chỉ riêng sꢀ an toàn của group multicast.
Quản lý thành viên :
Một group về phương diện logic là một cây multicast có gốc là “điểm gặp", mỗi
khi có một node mới được join vào group thì nó sẽ trở thành một thành viên của group
cũng như trở thành một thành phần của cây multicast, vì thế phải có cơ chế hợp lý để
tổ chức, quản lý các thành viên của group. Nếu một node Scribe là một phần của group
thì về phương diện cây multicast thì nó là một forwarder. Mỗi một forwarder duy trì
một bảng gọi là children table mà mỗi entry của bảng này sẽ gồm có 2 trường: địa chỉ
ip của một node “con” nào đó của nó (ip addr), và nodeId tương ứng của node con đó.
Join group:
Khi một node muốn join vào một group nào đó nó sẽ thꢀc hiện các bước sau:
Gửi thông điệp JOIN với groupId của group cần join làm key: route
(JOIN,groupId).
Giao thức Pastry sẽ định tuyến nó tới “điểm gặp”
- Nếu node trung gian trong quá trình truyền thông điệp là một forwarder (một
thành phần của group đang định join vào) thì đơn giản chỉ là thêm node cần join vào
làm một con của node forwarder này.
- Nếu node trung gian không phải là một forwarder của group cần join vào thì
thꢀc hiện các bước:
Tạo một children table cho node trung gian và thêm thông tin của node cần join
vào bảng này.
Gửi thông điệp JOIN của node trung gian tới điểm gặp (lúc này thay cho việc
thꢀc hiện join node ban đầu ta đi join node trung gian vào group). Và cứ thꢀc
hiện đệ quy như thế này ta sẽ có được một danh sách các node mới join vào
group thay vì chỉ một node ban đầu.
18
Để dễ hiểu ta xét ví dụ sau : một group có điểm gặp là node A có nodeId = 1100
(như hình vẽ ở dưới)
Hình 10. Quá trình 1 node join vào group
Node B có nodeId là 0111 muốn join vào group có A là gốc. nó sẽ gửi gói tin
route(JOIN,x) với x là groupId của group này, giao thức Pastry sẽ định tuyến gói tin
tới node D có nodeId là 1001. Nhưng node D không phải là một thành phần của group
này cho nên D sẽ tạo ra một children table của nó và thêm vào đó entry
(122.145.1.23;0111). Tiếp đó D sẽ gửi gói tin yêu cầu join vào group có gốc là A:
route(JOIN,x). Tiếp tục giao thức Pastry lại định tuyến nó tới node E và E cũng không
phải là thành viên của group này vì thế E cũng sẽ tꢀ tạo ra một childeren table của nó
và thêm vào entry (172.16.2.13;1001) Và sau đó E gửi gói tin route(JOIN,x). Gói tin
này tiếp tục được định tuyến và tới được A vì A là một thành của group cho nên ở đây
A sẽ thêm entry (10.10.1.123;1101) vào children table của nó. Kết quả là ta sẽ có thêm
3 thành phần mới của group là B ,D, E.
Tiếp theo node C có nodeId là 0100 muốn join vào group này. Để bắt đầu nó
cũng sẽ gửi gói tin yêu cầu route(JOIN,x) gói tin này được định tuyến tới node D và vì
bây giờ D đã là một thành phần của group này nên đơn giản D sẽ thêm vào children
table của nó một entry mới (123.134.12.12;0100).
Leave group:
Khi một node nào đó muốn rời khỏi group nó sẽ ghi một cách cục bộ rằng nó đã
rời khỏi group (tức là chỉ một mình nó biết nó đã rời khỏi mạng). Sau đó nếu bảng
children table của node này là rỗng tức là nó không có con trong cây multicast thì nó
sẽ gửi thông điệp LEAVE tới cha của nó trong cây multicast. Thông điệp này sẽ được
đệ quy trong cây multicast cho tới khi nó tới một node mà node có con đã rời khỏi
group. Còn nếu bảng children table của node muốn rời mạng không rỗng thì nó làm
19
như trong trường hợp nó không có con nào cả. Sau đó các con của nó sẽ xem như nó bị
lỗi và thꢀc thi theo cơ chế sửa lỗi (sẽ trình bày ở dưới).
Với cách join và leave group như thế này và với đặc tính phân phối ngẫu nhiên
của Pastry cây multicast sẽ được xây dꢀng một cách đồng đều theo nghĩa là không một
node nào trong cây multicast ngay cả node gốc chịu quá nhiều kiết nối tới các node
khác. Việc này giúp cho Scribe có khả năng mở rộng về kꢁch thước cũng như về khả
năng, tức là cả khi tăng số lượng node trong group hay là tăng các gói mulicast gửi đến
mạng thì Scribe vẫn có thể đảm đương được.
Truyền multicast tới mạng :
Khi một node nào đó muốn truyền multicast tới các điểm trong một group nào đó
nó sẽ gửi thông điệp multicast tới điểm gặp (route(MULTICAST,rootId)). Sau khi
điểm gặp nhận được thông điệp này nó sẽ gửi trả lại node kia Ip của nó (rootIP), sau
đó node này sẽ truyền thông tin muốn gửi tới điểm gặp. Điểm gặp sẽ sẽ copy gói tin
multicast này gửi cho các con của nó trong cây multicast (nếu có), các điểm con này
khi nhận được dữ liệu cũng lại tiếp tục copy dữ liệu đó và gửi tới các con của nó trong
cây (nếu có). Cứ lặp đi lặp lại như vậy và chỉ dừng lại việc này khi dữ liệu tới các node
là node lá của cây.
Hình 11. Truyền tin multicast trong group Scribe
Giả sử như hình vẽ ở trên Sender là node cần gửi dữ liệu cho cây multicast có
gốc là 1100. Nó sẽ gửi gói tin route(MULTICAST,1100), node 1100 nhận được gói tin
và trả lại cho sender địa chỉ ip của nó từ lúc này sender giao tiếp với node gốc này
thông qua ip (bây giờ là quan hệ trong giao thức tcp/ip chứ không liên quan gì đến
pastry hay p2p gì cả). Sender gửi dữ liệu cho node gốc 1100 node này sẽ tạo một bản
sao dữ liệu và gửi cho con của nó là 1101. Node 1101 nhận được dữ liệu từ root, nó
cũng sẽ tạo một bản sao và gửi cho 1001 là con của nó. Node 1001 lại tiếp tục copy dữ
liệu và gửi cho 0111 và 0100 là thành viên trong bảng children table của nó. Khi các
20
node 0100 và 0111 nhận được giữ liệu thì vì nó là lá của cây multicast nên nó không
làm gì nữa.
Trong vấn đề truyền dữ liệu multicast này có một điểm thú vị là khi sender muốn
gửi dữ liệu multicast tới group nó lại phải xin và nhận IP của node gốc rồi để sau đó
giao tiếp với node này dꢀa vào IP mà không sử dụng luôn giao thức Pastry để gửi dữ
liệu. Đơn giản là việc định tuyến cũng như gửi tin thông qua Pastry là một việc rất tốn
thời gian và tài nguyên mạng, mà bình thường một sender không chỉ gửi một gói tin
multicast tới mạng, mà nó sẽ gửi một số hoặc nhiều gói, do đó việc sender lưu IP của
node root và gửi gói tin trꢀc tiếp sẽ tiết kiệm được thời gian cũng như tài nguyên của
mạng. Tuy nhiên nếu node gốc bị lỗi hoặc bị rời khỏi mạng thì sender phải tìm lại IP
của node root mới và tiếp tục việc truyền thông tin
Sửa cây multicast
Vì Scribe làm việc trong môi trường mạng mang, do đó muốn duy trì được sử ổn
định của group, phải có những cơ chế hợp lý để giải quyết các vấn đề thường gặp phải
trong mạng ngang hàng. Phần này sẽ đi sâu vào việc làm sao để sửa chữa một cây
multicast khi một node bị rời khỏi mạng.
Trong Scribe node cha sẽ định kỳ gửi các gói tin hearbeat tới node con của nó
nhằm thông báo sꢀ tồn tại của mình trong cây. Nếu node con không nhận được gói tin
heartbeat do cha nó gửi tới trong một thời gian nào đó, nó sẽ xem như node cha của nó
bị lỗi. Và nó sẽ tꢀ động tìm một node cha khác thay thế, bằng cách gửi thông điệp
JOIN với key là groupId của group hiện tại (quá trình này giống với quá trình join vào
group).
Hình 12. Quá trình tự sửa cây multicast
21
Giả dụ như hình vẽ trên ban đầu ta có cây multicast với gốc là node 1100 trong
cây node 1001 có cha là node 1101. Khi node 1001 không nhận được heartbeat của
1101 trong một khoảng thời gian nào đó nó sẽ xem như 1101 bị lỗi và nó sẽ tꢀ động
gửi gói tin route(JOIN,groupId). Tiếp theo giống như trong quá trình jon group. Cây
multicast sẽ được xây dꢀng lại và bây giờ thì node 1001 nhận một node mới là 1111 là
cha mới của nó (như hình vẽ).
Trong trường hợp node gốc bị lỗi. Thì các con của nó cũng sẽ chạy giải thuật như
trên khi đó giải thuật Pastry sẽ tꢀ chọn ra một node gốc mới có nodeId gần nhất (tính
theo hiện thời) với groupId và group sẽ lại được duy trì như bình thường.
Vì khả năng chống lỗi cao như thế này, Scribe luôn có tính sẵn sàng cao và
chống chịu lỗi tốt, cho dù có nhiều node lỗi cùng một lúc thì sau một thời gian ngắn
cây multicast lại được xây dꢀng lại và ổn định như trước.
Splitstream
Splistream có thể xem như là việc chọn lꢀa các cây Scrbie để tạo nên cây
multicast đa luồng. Việc chọn lꢀa các cây Scribe sẽ dễ dàng tạo nên cây multcast đa
luồng với tính chất : 1 node là node trong của 1 luồng sẽ là node lá trong các luồng còn
lại
Hình 13. Splitstream F luồng
Việc xây dꢀng các luồng là khá đơn giản. Như ở trên hình 3 với không gian
Pastry được đánh địa chỉ các node gồm F ký tꢀ. Splitstream sẽ chọn ra các luồng có
tên là 0x , 1x , … Fx để các node sau khi gia nhập vào cây multicast đa luồng có thể
đảm bảo. Node có id bắt đầu là 0x sẽ là node trong của cây multicast stripeId 0x và là
node lá của tất cả các luồng còn lại. Tương tꢀ Node có id bắt đầu là 1x se là node trong
của cây multicast stripeId 1x và là lá của tất cả các luồng còn lại…
22
Tuy nhiên Splitstream sẽ gặp vấn đề tại các máy( peer ) tham gia mà nếu chỉ đơn
thuần lꢀa chọn các cây Scribe để truyền các luồng vào thì là chưa đủ đáp ứng tính chất
multicast :
Không giới hạn dc băng thông đi ra của 1 peer do nhu cầu join của các peer
khác: khi 1 peer đã bị vượt quá băng thông giới hạn đi ra thì các peer khác vẫn
muốn gia nhập vào luồng của peer này. Nếu vẫn duy trì cơ chế như cây Scribe
thì sẽ có 1 số peer thật sꢀ không nhận được dữ liệu từ 1 vài luồng do node cha
của nó không gửi dữ liệu thꢀc sꢀ đến cho nó
Splistream sử dụng cơ chế mới để giải quyết vấn đề tại các node mà băng thông
đi ra đã bị vượt quá giới hạn. Cơ chế này bao gồm các bước :
B1. Xác định node cha:
Hình 14. Xác định node cha khi băng thông đi ra vượt quá giới hạn
Trong ví dụ trên node với id 080* đã bị limit outdegree ( băng thông đi
qua vượt quá giới hạn ) thì nhận được yêu cầu join vào của node với id 001* ở
luồng 0800. Node 080* sẽ xem xét lại tất cả các node con của nó để loại đi 1
node con. Hình 14.(1)-(2) là trường hợp có node con 9* nhận node 080* làm
cha trong luồng 1800 khác với luồng 0800. Node 080* sẽ nhận node 001* làm
con và loại bỏ node 9*. Sau đó node 085* lại yêu cầu join vào node 080* .Hình
14.(3)-(4) là trường hợp các node con đều nhận 080* là cha trong luồng 0800 ,
xét đến id của các node con. Node 001* la node có id với số ký tꢀ tính từ trái
23
sang phải khác với luồng 0800 nhất. Node 001* sẽ trở thành node orphan và
node 085* được nhận làm node con.
B2. Nếu sau Bước 1 vẫn có node orphan (tức là node chưa tìm được node cha)
sẽ tiến hành bước này. Node orphan sẽ gửi unicast đến SCG (Spare Capacity
Group) để tìm được node cha. SCG là tập hợp tất cả các node mà băng thông đi
ra chưa vượt quá giới hạn . Với cơ chế truyền unicast , node orphan sẽ gửi
thông điệp tìm node có luồng mà băng thông đi ra chưa vượt quá giới hạn để
nhận nó làm node cha.
̉
Ƣu điêm : xây dưṇ g cây multicast đa luồng kha đơn gian dưạ vao kết cấu có sẵn
̉
́
̀
̉
của Pastry và Scribe. Khi maṇ g ôn điṇ h và việc phân chia định danh là khá đều thì các
node trong hê ̣thống chiụ tai tương đương nhau . Thêm vao đo la cac cơ chế tim node
̉
̀
́ ̀ ́
̀
cha nhằm đam bao cac node trong maṇ g không bi ̣qua tai.
̉
̉
̉
́
́
̉
Nhƣơc̣ điêm : không đam bao đươc̣ độchênh lêc̣ h độtrễcac luồng nhâṇ đươc̣ taị
̉
̉
́
các node là nhỏ do việc tạo cây Scribe mang tꢁnh ngẫu nhiên dꢀa chủ yếu vào kết cấu
bên dươi cua Pastry.
̉
́
24
Chƣơng 3.Xây dựng cây multicast đa luồng thời gian thực
trên mạng ngang hàng có cấu trúc
Sau khi đã nghiên cứu các giải pháp hiện nay về truyền tin multicast đa luồng với
các ưu nhược điểm riêng khi ứng dụng sang truyền tin multicast đa luồng thời gian
thꢀc thì ở chương ba này sẽ là giải pháp mà tôi đưa ra trong khóa luận. Giải pháp này
đã hướng đến mục tiêu là truyền tin multicast đa luồng thời gian thꢀc ngay từ đầu nên
nó sẽ có những ưu điểm riêng. Tuy nhiên bên cạnh đó cũng có những nhược điểm nhất
định. Phần đánh giá về chương trình mô phỏng sẽ được trình bày ở chương bốn. Giải
pháp này được xây dꢀng dꢀa trên giao thức DHT tham khảo bảng định tuyến của
Chord..
3.1.Vấn đề cần giải quyết
Mục tiêu lớn nhất khi xây dꢀng cây multicast đa luồng thời gian thꢀc trong mạng
ngang hàng có cấu trúc là:
Xây dꢀng cây multicast đa luồng
Duy trì cây mulitcast khi mạng thay đổi
Cân bằng băng thông đi ra tại các node trong mạng : hạn chế các node không
gửi dữ liệu cho node nào , các node phải gửi nhiều hơn số luồng giới hạn là
không quá lớn
Độ trễ của một node khi nhận được tất cả các luồng là nhỏ
Chênh lệch độ trễ tại một node giữa luồng nhận được sớm nhất và nhận được
muộn nhất là nhỏ (đây chꢁnh là mục tiêu quan trọng nhất của thiết kế)
Trong khuôn khổ khóa luận giới hạn nên giải pháp của tôi đưa ra mới chỉ là bước
đầu , chưa được tối ưu hóa để có thể đáp ứng tất cả các vấn đề cần giải quyết. Quá
trình chạy chương trình mô phỏng tuy chưa được tốt như mong muốn nhưng đã cho
thấy kết quả khả quan và cho thấy khả năng phát triển của giải pháp này.
3.2.Ý tƣởng
Ý tưởng đưa ra được dꢀa trên thiết kế chính của Chord với các ưu điểm:
25
Tải về để xem bản đầy đủ
48 trang
04/05/2025
1330
Bạn đang xem 30 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_truyen_tin_multicast_da_luong_thoi_gian_thuc_tren.pdf
