MỤC LỤC
ƯƠ

Ớ

1 .............................................................................................................................. 6
THIỆU .................................................................................................................... 6
.1
.2
.3

ƯƠ

ĐỊ

Tổng quan ........................................................................................................... 6
Mục tiêu và phạm vi ........................................................................................... 8
Tổ chức luận văn ................................................................................................. 8

2 .............................................................................................................................. 9
NGHĨA, KIẾN THỨC CƠ BẢN............................................................................ 9
Một vài mơ hình mạng cơ bản ............................................................................ 9
.1.1
Mơ hình client-server .................................................................................. 9
.1.1.1
Những điểm thuận lợi ............................................................................. 9
.1.1.2
Những hạn chế ...................................................................................... 10
.1.2
Mơ hình IP multicast ................................................................................. 10
.1.2.1

Những thuận lợi .................................................................................... 10
.1.2.2
Hạn chế ................................................................................................. 10
.1.3
Mạng peer-to-peer (P2P)........................................................................... 10
.2
Sự ra đời của kỹ thuật ALM, và phân loại ........................................................ 11
.2.1
Sự ra đời của kỹ thuật ALM ..................................................................... 11
.2.2
Phân loại ALM .......................................................................................... 13
.1

ƯƠ

Ấ

3 ............................................................................................................................ 14
ĐỀ VÀ CÁC GIẢI PHÁP LIÊN QUAN ............................................................. 14
.1
.2

Một số vấn đề đối với ứng dụng Internet TV ................................................... 14
Một số giải thuật truyền dữ liệu phân tán 1-to-N.............................................. 14
.2.1
ALMI ........................................................................................................ 14
.2.1.1
Giới thiệu .............................................................................................. 14
.2.1.2
Giải thuật thêm một thành viên mới vào hệ thống ................................ 15

.2.1.3
Cách duy trì cây .................................................................................... 16
.2.1.4
Cách truyền dữ liệu trong hệ thống ....................................................... 17
.2.1.5
Một số đặc điểm của ALMI .................................................................. 17
.2.2
CAN .......................................................................................................... 17
.2.2.1
Giới thiệu .............................................................................................. 17
.2.2.2
Giải thuật một peer tham gia vào CAN ................................................ 17
.2.2.3
Cách duy trì các peer trong CAN .......................................................... 18
.2.2.4
Cách truyền dữ liệu trong CAN ............................................................ 19
.2.2.5
Đặc điểm ............................................................................................... 19
.2.3
HMTP (Host Multicast Tree Protocol) ..................................................... 20
.2.3.1
Giới thiệu .............................................................................................. 20
.2.3.2
Giải thuật một thành viên gia nhập vào hệ thống ................................. 21
.2.3.3
Cách duy trì những thành viên trong nhóm .......................................... 21
.2.3.4
Cách truyền dữ liệu ............................................................................... 21
.2.3.5
Đặc điểm ............................................................................................... 21

.2.4
NICE ......................................................................................................... 22
.2.4.1
Giới thiệu .............................................................................................. 22
1


.2.4.2
Giải thuật gia nhập một thành viên mới ................................................ 22
.2.4.3
Cách duy trì và giải thuật một thành viên rời khỏi nhóm ..................... 24
.2.4.4
Cách truyền dữ liệu trong NICE ........................................................... 24
.2.4.5
Đặc điểm ............................................................................................... 24
.2.5
Scribe/Pastry ............................................................................................. 24
.2.5.1
Pastry protocol ...................................................................................... 25
.2.5.2
Giải thuật một peer tham gia vào Pastry ............................................... 26
.2.5.3
Scribe .................................................................................................... 27
.2.5.4
Giải thuật một peer tham gia vào scribe ............................................... 27
.2.5.5
Đặc điểm ............................................................................................... 27
.3
Một vài loại hệ thống P2P live streaming ......................................................... 27
.3.1

Hệ thống P2P live streaming có cấu trúc .................................................. 27
.3.1.1
Một cây đơn .......................................................................................... 28
.3.1.2
Nhiều cây .............................................................................................. 28
.3.2
Hệ thống P2P live streaming khơng có cấu trúc ....................................... 29
.4
Một vài giải pháp P2P live streaming ............................................................... 29
.4.1
Giải pháp P2PCast .................................................................................... 29
.4.1.1
Mục tiêu ................................................................................................ 30
.4.1.2
Môi trường và những giả định .............................................................. 30
.4.1.3
Những nguyên tắc thiết kế .................................................................... 31
.4.1.4
Giao thức P2Pcast ................................................................................. 31
.4.1.4.1
Giải thuật một peer tham gia vào hệ thống ..................................... 32
.4.1.4.2
Giải thuật xóa một peer từ hệ thống................................................ 35
.4.1.5
Kiến trúc của P2Pcast ........................................................................... 36
.4.2
Giải pháp PULSE ...................................................................................... 36
.4.2.1
Khái niệm chung ................................................................................... 37
.4.2.1.1

The stream ....................................................................................... 37
.4.2.1.2
Quản lý tri thức ............................................................................... 38
.4.2.1.3
Trao đổi chunk trong hệ thống ........................................................ 38
.4.2.1.4
Lựa chọn chunk ............................................................................... 39
.4.2.2
Giải thuật ............................................................................................... 40
.4.2.2.1
Một peer tham gia vào hệ thống ..................................................... 40
.4.2.2.2
Quản lý peers trong hệ thống .......................................................... 41
.4.2.2.3
Việc đồng bộ thời gian giữa các peers trong hệ thống.................... 43
.4.2.2.4
Lựa chọn peer để gửi Red Message ................................................ 44
.4.2.2.5
Việc trao đổi chunk trong hệ thống................................................. 45
.4.2.2.6
Một peer rời khỏi hệ thống ............................................................. 45
.4.2.3
Kiến trúc của hệ thống .......................................................................... 46
.5
Đánh giá ............................................................................................................ 48
ƯƠ

Ả

4 ............................................................................................................................ 49

PHÁP PULSE CẢI TIẾN ..................................................................................... 49
.1
.2
.3

Tổng quan ......................................................................................................... 49
Một vài hạn chế đối với giải pháp PULSE ....................................................... 49
Giải pháp cải tiến .............................................................................................. 50
.3.1
Xây dựng server để quản lý peers trong hệ thống .................................... 50
.3.2
Giải thuật một peer tham gia vào hệ thống ............................................... 51
2


.3.3
.3.4
ƯƠ

Giải thuật một peer rời khỏi hệ thống ....................................................... 52
Trao đổi chunk trong hệ thống .................................................................. 52

5 ............................................................................................................................ 53
SÁNH, ĐÁNH GIÁ .............................................................................................. 53
Đánh giá số lượng thông điệp ........................................................................... 53
Ưu điểm ............................................................................................................ 54
.2.1
Về mặt giải thuật ....................................................................................... 54
.2.2
Về mặt sử dụng ......................................................................................... 55

.3
Nhược điểm....................................................................................................... 55
.1
.2

ƯƠ

Ế

À

Ụ

Ụ

6 ............................................................................................................................ 56
LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................................... 56
LIỆU THAM KHẢO ............................................................................................ 58
LỤC A: Định dạng thông điệp.............................................................................. 60
LỤC B: Pulse file .................................................................................................. 66

3


DANH MỤC HÌNH
ình

ình

ình


ình

ình

ình

2.1: Mơ hình mạng client- ..................................................................................... 9
2.2: Mơ hình mạng IP ......................................................................................... 10
2.3: Mơ hình mạng ............................................................................................... 11
2.4: ALM dùng Multiple ..................................................................................... 12
2.5: ALM dùng lớp mạng bao ............................................................................. 12
ủ

2.6: Phân loại kỹ thuật ......................................................................................... 13

(a) N yêu cầu gia nhập và nhận những chỉ dẫn từ peer điều ................................ 15
ển

(b) N khảo sát những node hiện có và gửi kết quả đển node điều ....................... 16
ển

(c) N được yêu cầu để làm con của C và cha của ................................................. 16
ình

ình

ình

ình


ình

ình

ình

ình

ình

ình

ình

ình

ình

ình

ình

ình

ình

3.1: Một peer tham gia vào hệ thống dùng giải thuật ......................................... 16
3.2: Một peer tham gia vào hệ thống dùng .......................................................... 18
3.3: Truyền dữ liệu dùng giải thuật ..................................................................... 19

3.4: Kiến trúc của ................................................................................................ 20
3.5: Kiến trúc của ................................................................................................ 22
3.6: Một peer tham gia vào hệ thống dùng .......................................................... 23
3.7: Truyền dữ liệu dùng giải thuật ..................................................................... 24
3.8: Bảng định tuyến Pastry cho peer với ID 0x65a1… ....................................... 25
3.9: Cách tìm đường đi trong .............................................................................. 26
3.10: Peer ngẫu nhiên là incomplete .................................................................. 33
3.11: Peer ngẫu nhiên là only-child .................................................................... 33
3.12: Peer ngẫu nhiên là complete ...................................................................... 34
3.13: Một peer rời khỏi hệ .................................................................................. 35
ống

3.14: Kiến trúc của .............................................................................................. 36
3.15: Cấu trúc bộ đệm dữ .................................................................................... 37
ệu

3.16: Lược đồ tuần tự một peer tham gia vào hệ ................................................ 40
ống

3.17: Lược đồ tuần tự về đồng bộ thời gian đối với contact ............................... 43
4


ình

ình

ình

ình


ình

ình

ình

ình

ình

ình

ình

ình

ình

3.18: Sắp xếp peer cho việc lựa chọn Red .......................................................... 44
3.19: Kiến trúc của .............................................................................................. 47
4.1: Tượng tác giữa source-server- ...................................................................... 50
4.2: Lược đồ tuần tự một peer tham gia vào hệ .................................................. 51
ống

A.1: Pulse message ............................................................................................. 60
A.2: Hello ........................................................................................................... 61
A.3: Blue ............................................................................................................. 61
A.4: Bye .............................................................................................................. 62
A.5: Synchronization .......................................................................................... 62

A.6: Red .............................................................................................................. 63
A.7: Data ............................................................................................................. 64
A.8: Hello temp .................................................................................................. 65
A.9: Response PULSE ........................................................................................ 65

5


CHƯƠNG 1
GIỚI THIỆU
1.1 Tổng quan
Từ những năm 90, Internet là một kênh chính để truyền bá thơng tin. Khi
Internet mới phát triển nó có rất nhiều hạn chế và khơng được mở rộng, băng
thông chỉ hổ trợ 56Kbps thông qua đường dây điện thoại. Từ năm 2000, những kỹ
thuật mới về Internet được ra đời và giúp cải thiện băng thông rất nhiều. Với sự
phát triển này, ngày nay Internet khơng chỉ là một kênh thơng tin mà nó cịn cung
cấp nhiều dịch vụ và ứng dụng cần băng thông rộng. Một trong những loại ứng
dụng yêu cầu Internet băng thông ộr ng là truyền dữ liệu đa truyền thông
(multimedia data).
Cách đơn giản nhất để truyền file đa truyền thông là thực hiện truyền một gói
những file này. Nội dung đơn giản chỉ là một file mà kích thước thì được xác định
tại nơi gửi. Người dùng muốn xem file này, họ phải lấy file này về trước khi xem
nó. Có nhiều cách để lấy file, có thể được lấy dựa vào ứng dụng client-server hay
dựa vào ứng dụng chia sẻ file của P2P (Peer-to-Peer), v.v.
Cũng có cách khác để truyền file đa truyền thơng, mà ở đó nội dung thì được
truyền thành những dịng dữ liệu liên tục từ nguồn. Người dùng khơng cần phải
lấy tồn bộ file trước khi xem mà chỉ cần tái tạo lại những dòng dữ liệu nhận được
và xem trực tiếp. Có hai cách để truyền dữ liệu liên tục: theo yêu cầu và live
streaming.
Dữ liệu truyền theo yêu cầu: nội dung của dữ liệu đa truyền thơng đã biết

trước kích thước và được lưu trữ tại một nguồn nào đó và có thể được lấy bất kỳ
khi nào. Khi người dùng muốn xem file này, họ tương tác với nơi chứa file này để
lấy. Vấn đề lớn nhất với cách này là người dùng phải đợi để tìm ra nơi chứa file
này.
Live streaming: hay còn gọi là truyền dữ liệu thời gian thực. V ới cách này
nội dung của dữ liệu đa truyền thơng sẽ được truyền đi ngay khi nó được tạo ra từ
nguồn mà không cần bất kỳ yêu cầu nào. Người xem phải xem những thông tin
này khi họ tham gia vào hệ thống. Với đặc điểm này, kích thước của dữ liệu khơng
được định trước vì vậy người xem sẽ khơng biết khi nào thì kết thúc. Khó khăn
lớn nhất với phương pháp này là thời gian trễ từ người xem so với nguồn.
Mơ hình client-server thì thích ợhp cho phương pháp truyền dữ liệu live
streaming, nhưng nó khơng thể hiện thực để đáp ứng khi số lượng người xem lớn.
Bởi vì server có lượng băng thơng cố định vì vậy nó chỉ phục vụ cho một lượng
người xem giới hạn nào đó.
Để khắc phục những hạn chế trên, kỹ thuật IP Multicast được xem là một
phương pháp tốt nhất để phân phối dữ liệu từ một nguồn đến một nhóm người
6


xem. Tuy nhiên việc phát triển IP Multicast có nhiều hạn chế. Đầu tiên nó yêu cầu
thay đổi những thiết bị trong mạng hiện có, điều này rất khó khăn, phức tạp và nó
tăng sự trùng lặp dữ liệu ở router bởi vì khơng phải tất cả các thiết bị trong mạng
đều hổ trợ sẵn IP Multicast. Ngoài ra, một l ý do quan trọng hơn cả là nhiều nhà
cung cấp dịch vụ đã tắt chức năng này, bởi vì họ không muốn người dùng dùng
dịch vụ của họ mà không trả tiền.
Từ đây ý tưởng xây dựng multica st ở mức ứng dụng [9] được hình thành.
Những gói dữ liệu khơng cịn được tái tạo tại các router mà nó sẽ được tái tạo tại
thiết bị tham gia vào mạng (hosts). Điều này sẽ giải quyết được những hạn chế về
thay đổi cơ sở hạ tầng của mơ hình IP Multicast và nó cũng giải quyết được vấn đề
về mở rộng đối với mơ hình client-server. Có nhiều ứng dụng đã phát triển dựa

trên kỹ thuật này.
Một kỹ thuật khác là dùng mạng P2P cho việc truyền dữ liệu live streaming.
Những peer trong mạng sẽ hoạt động như những client và s erver tại cùng thời
điểm. Hệ thống P2P live streaming tổ chức những peer thành những lớp bao phủ
để nhắm tới những vấn đề sau:
 Sự phân tán: khơng có sự tập trung, phải có được sự cộng tác của những
peer tham gia vào, một công việc của mỗi peer thì được hồn thành một cách
cục bộ. Với đặc điểm này hệ thống khơng có vấn đề về giới hạn tài nguyên,
đồng thời một peer chết không là nguyên nhân của cả hệ thống chết.
 Chất lượng của đường truyền dữ liệu: từ đây dữ liệu được nhân bản tại
những host vì vậy nó tăng độ an tồn cho dữ liệu , trong những hệ thống này
đường truyền dữ liệu từ nguồn tới những peer thì khác nhau vì vậy chất lượng
của đường truyền phụ thuộc vào số peer tham gia vào hệ thống.
 Độ ổn định: host thì ítổn định hơn so với router và những thiết bị mạng
khác, vì host có thể tham gia hay rời hệ thống bất kỳ lúc nào, thậm chí là một
peer có thể chết rất dễ dàng khi tham gia vào hệ thống. Vì vậy những hệ thống
này cần phải hạn chế sự ảnh hưởng của một peer tham gia vào và rời khỏi hệ
thống.
 Thông điệp điều khiển: hệ thống cần có những thơng điệp điều khiển để
duy trì hệ thống. Vấn đề là làm sao để giảm số lượng thông điệp điều khiển
trao đổi giữa các peer.
 Khả năng thích nghi: điều này thì liên quan tới tính khơng đồng nhất của
những peer trong hệ thống. Những host có thể có lượng tài nguyên khác nhau.
Những hệ thống này phải khám phá tất cả những tài nguyên sẵn có của những
peer tham gia vào hệ thống.
 Sự công bằng: những ứng dụng này phải quan tâm tới sự công bằng, hệ
thống nhắm tới việc một peer muốn tải dữ liệu thì nó phải đóng góp vào việc
truyền dữ liệu.
7



 Nội dung: nội dung phải được nhân bản tại host, và nó có thể truyền cho
những peer khác trong một khoảng thời gian nào đó. Vấn đề mất dữ liệu và
chậm trễ phải được xem xét.
Từ đây cho thấy kỹ thuật mạng P2P thì phù hợp với ứng dụng live streaming.
Hiện nay đã có những ứng dụng live streaming dùng kỹ thuật mạng này như
P2Pcast [12], giải pháp dùng mạng P2P có ấcu trúc và PULSE [ 20], giải pháp
mạng P2P khơng có cấu trúc. Với khả năng dễ mở rộng của giải pháp PULSE thì
nó phù hợp hơn với yêu cầu của ứng dụng Internet TV.
Tuy nhiên vẫn còn một vài hạn chế của giải pháp PULSE như vấn đề quá tải
ở nguồn bởi vì một peer muốn tham gia vào hệ thống thì nó phải tương tác với
nguồn, số lượng thông điệp trao đổi quá nhiều và tăng theo số lượng peer hiện có
trong hệ thống mà nó có thể ảnh hưởng đến băng thơng, ngồi ra vấn đề khơng
đồng nhất thơng tin cấu hình có thể là nguyên nhân một peer không thể tham gia
vào hệ thống thành công.

1.2 Mục tiêu và phạm vi
Mục tiêu của đề tài là đưa ra một giải pháp cải tiến từ giải pháp PULSE để
khắc phục những hạn chế trên của giải pháp PULSE. Đề tài sẽ chú trọng việc tham
gia và rời hệ thống rất nhanh của một số peer. Ngồi ra, đề tài cũng giảm thiểu
lượng thơng điệp điều khiển trao đổi. Mà cụ thể, khi một peer tham gia vào hệ
thống nó sẽ liên lạc với một peer ngẫu nhiên (contact peer) từ những peer đang tồn
tại trong hệ thống. Đồng thời, peer này chỉ kết nối và nhận dữ liệu tạm thời từ
contact peer trong khoảng thời gian qui định.
Với những cải tiến này, vấn đề quá tải ở nguồn cũng như không đồng nhất
dữ liệu đã được giải quyết. Đồng thời số lượng thông điệp điều khiển khi một peer
tham gia vào hay rời hệ thống rất nhanh là một hằng số thay vì phụ thuộc vào số
lượng peer hiện có trong hệ thống.

1.3 Tổ chức luận văn

Phần còn lại của luận văn được chia thành 5 chương như sau:
Chương 2: định nghĩa, kiến thức cơ bản.
Chương 3: vấn đề và các giải pháp liên quan.
Chương 4: giải pháp PULSE cải tiến.
Chương 5: so sánh, đánh giá.
Chương 6: kết luận, hướng phát triển.

8


CHƯƠNG 2
ĐỊNH NGHĨA, KIẾN THỨC CƠ BẢN
2.1 Một vài mô hình mạng cơ bản
2.1.1 Mơ hình client-server
Client-server là một mơ hình khá phổ biến. Trong mơ hình này có một server
trung tâm, tất cả các client phải giao tiếp với server này. Dữ liệu được truyền trực
tiếp từ server đến client và ngược lại mà không thông qua bất kỳ client trung gian
nào.

Hình 2.1: Mơ hình mạng client-server

2.1.1.1 Những điểm thuận lợi
 Tất cả dữ liệu được lưu trữ trên máy chủ vì vậy nó có tính bảo mật cao.
Ngồi ra nó cịn điều khiển việc truy xuất dữ liệu của máy Client.
 Dữ liệu được lưu trữ tập trung vì vậy dễ dàng cho việc cập nhập dữ liệu
mới khi cần thiết.
9


2.1.1.2 Những hạn chế

 Tắt nghẽn đường truyền trong mạng.
 Dữ liệu chỉ được lưu trên một máy chủ vì vậy có thể dẫn đến việc mất mát
dữ liệu trên đường truyền.

2.1.2 Mơ hình IP multicast
IP Multicast là một kiểu truyền dữ liệu mới trên mạng, dữ liệu đượ c truyền
từ một peer đến một nhóm các peer cịn lại. Việc thực hiện truyền nhận hay định
tuyến dựa vào lớp 3 trong mơ hình OSI.

Hình 2.2: Mơ hình mạng IP Multicast

2.1.2.1 Những thuận lợi
 Hiệu quả về mặt truyền dữ liệu.
 Dữ liệu được truyền nhanh hơn so với mô hình Unicast.

2.1.2.2 Hạn chế
 Khó quản lý mạng.
 Khó mở rộng.
 Khó giải quyết được những vấn đề tắt nghẽn.
 Chưa có khả năng chịu đựng lỗi.

2.1.3 Mạng peer-to-peer (P2P)
Mạng P2P khai thác kết nối giữa những thành viên trong mạng và tận dụng
băng thông của những thành viên tham gia vào mạng hơn là tập trung tài nguyên ở
máy chủ. Mạng này thì hữu dụng cho nhiều ứng dụng: file sharing, video
streaming …
Một mạng P2P nguyên gốc không tồn tại khái niệm máy chủ và máy khách
riêng lẻ, chỉ tồn tại những peers ngang hàng nhau, m
ột pee r mô phỏng cả chức
năng client và server đối với những peer khác trong mạng.


10


Hình 2.3: Mơ hình mạng P2P

2.2 Sự ra đời của kỹ thuật ALM, và phân loại
2.2.1 Sự ra đời của kỹ thuật ALM
Có nhiều cách để truyền dữ liệu trong mạng như: unicast, broadcast. Unicast
là cách truyền dữ liệu giữa hai peer. Broadcast là cách truyền dữ liệu từ một peer
đến tất cả những peer khác mà nằm trong cùng mạng với nó. Với unicast, tốc độ
truyền dữ liệu chậm, trong khi đó broadcast thì truyền dữ liệu đến những peer mà
có thể chúng khơng mong muốn để nhận, ngồi ra nó cịn là ngun nhân tắt
nghẽn đường truyền. Vì vậy người ta đã đưa ra một phương pháp mới để truyền
dữ liệu từ một peer đến những peer mà nằm trong cùng nhóm với nó. Phương
pháp này gọi là Multicast . Tuy nhiên với IP Multicast chúng ta có một số hạn chế
về việc mở rộng, điều khiển lỗi vì vậy nó khơng phù hợp cho những ứng dụng như
internet TV.

11


Vì vậy một kỹ thuật mới được ra đời nhằm khắc phục những hạn chế của IP
Multicast. Đó là Multicast ở mức ứng dụng (ALM – Application Level Multicast).
Với ALM, nó di chuyển việc định tuyến từ lớp mạng đến lớp ứng dụng trong mơ
hình OSI. Vì vậy nó khơng phụ thuộc vào cơ sở hạ tầng của mạng.
Hiện nay có hai kỹ thuật để hiện thực ALM: multiple Unicast và overlay
Network.
Multiple Unicast là một kỹ thuật phức tạp nhất trong tất cả các kỹ thuật của
ALM và thông thường nó khơng được xem là một loại của ALM. Nhưng những

đặc điểm và chức năng của nó cũng được xem như là ALM.

Hình 2.4: ALM dùng Multiple Unicast
Multiple unicast có rất nhiều hạn chế: chi phí, khả năng mở rộng, dễ gây ra
hiện tượng thắt nút cổ chai.
ALM dùng lớp mạng bao phủ. Với kỹ thuật này mỗi peer không chỉ nhận dữ
liệu mà còn phải truyền cho những peer khác, vì vậy hệ thống sẽ tận dụng tài
nguyên của thành viên tham gia vào hệ thống, chi phí sẽ được phân bố đến những
peer thay vì tập trung trên server. Tất cả những kỹ thuật này có chung đặc điểm là
xây dựng lớp mạng bao phủ peer-to-peer.
Chính vì những đặc điểm vượt trội của ALM dùng lớp mạng bao phủ vì vậy
đề tài sẽ dựa trên kỹ thuật này để phát triển ứng dụng internet TV và trong những
phần tiếp theo ALM có nghĩa là ALM dùng lớp mạng bao phủ.

Hình 2.5: ALM dùng lớp mạng bao phủ

12


2.2.2 Phân loại ALM
Bằng việc xem xét những đặc điểm của ALM người ta phân ALM thành
những loại chính như sau:
Điều khiển tập trung: xây dựng một lớp mạng bao phủ được điều khiển bởi
một peer đơn. Việc duy trì và xây dựng lớp mạng bao phủ dựa trên chỉ số thu thập
được từ những peer trung gian khác trong nhóm.
Điều khiển phân tán: xây dựng một lớp bao phủ mà xử lý phân tán.
Dựa vào cây: những peer tham gia vào hệ thống được xây dựng theo mơ hình
cây, dữ liệu được truyền từ source đến những peer trong hệ thống theo mơ hình
cây. Trong mơ hình này khái niệm cha con khơng có ý nghĩa tro ng việc truyền dữ
liệu.

Dựa vào lưới: xây dựng và truyền dữ liệu trong hệ thống dựa vào lưới.
Dựa vào cơ sở hạ tầng định tuyến: xây dựng lớp bao phủ mà dùng đỉa chỉ
của peer để xây dựng bảng đường đi của những peer trong hệ thống.
Dựa vào hệ tọa độ: xây dựng lớp bao phủ bằng việc ánh xạ mỗi peer tương
ứng với một điểm trong hệ tọa độ.

Hình 2.6: Phân loại kỹ thuật ALM

13


CHƯƠNG 3
VẤN ĐỀ VÀ CÁC GIẢI PHÁP LIÊN QUAN
3.1 Một số vấn đề đối với ứng dụng Internet TV
Internet TV ngày càng trở nên phổ biến, tuy nhiên việc phát tr iển ứng dụng
internet TV phải đảm bảo những tính năng bên dưới:
 Dữ liệu phải được truyền liên tục.
 Hệ thống nên dễ mở rộng, không hạn chế số lượng thành viên.
 Tránh vấn đề tắt nghẽn đường truyền.
 Giảm thiểu chi phí của một peer khi nó tham gia vào hệ thống.
 Hệ thống phải có khả năng chịu đựng lỗi cụ thể khi một peer trong hệ thống
chết thì hệ thống vẫn hoạt động bình thường với những peer còn lại.
 Sự đồng bộ, chia sẻ tài nguyên của những peers trong hệ thống.
 Việc chuyển kênh liên tục của người dùng
 Chất lượng hình ảnh.
 Độ chậm trễ so với nguồn phát.
Trong chương này sẽ trình bày một vài giải thuật truyền dữ liệu phân tán 1 to-N, cũng như một vài phương pháp truyền dữ liệu dùng kỹ thuật P2P . Sau đó
đưa ra những giải pháp hiện có dùng kỹ thuật P2P để truyền d ữ liệu đa truyền
thông live streaming cũng như những đánh giá cho mỗi giải pháp từ đó chọn một
giải pháp mà phù hợp với ứng dụng Internet TV. Sau đó tìm hiểu những hạn chế

của giải pháp này và đưa ra một giải pháp cải tiến.

3.2 Một số giải thuật truyền dữ liệu phân tán 1-to-N
3.2.1 ALMI
3.2.1.1 Giới thiệu
ALMI [1] dùng phương pháp điều khiển tập trung dựa trên mơ hình cây để
bảo đảm sự nhất qn và tính hiệu quả đối với tất cả các thành viên trong nhóm.
Một phiên giao dịch của ALMI gồm có một thành phần điều khiển giao dịch
và những thành viên tham gia giao dịch.
Thành phần điều khiển giao dịch thông thường là một thực thể của chương
trình và nên được đặt ở những nơi mà những thành viên tham gia giao dịch có thể
truy xuất dễ dàng. Nó thơng thường là server. Nó khơng tham gia vào q trình
14


truyền dữ liệu. Nó chỉ có tác dụng cho phép đăng ký thành viên mới, thành viên
muốn rời khỏi nhóm hay trong trường hợp một thành viên bị chết đột ngột. Nó
cũng trao đổi với những thành viên dùng thơng điệp điều khiển để duy trì cây
multicast.
Những thành phần tham gia giao dịch được tổ chức, sắp xếp vào một cây
multicast. Giữa những thành phần này được liên kết với nhau thông qua kết nối
unicast. Một thành viên nhận được dữ liệu nó sẽ truyền đến những thành viên kế
cận. Ngồi ra một thành viên cịn có khả năng giám sát một nhóm các thành viên
khác nếu được nhận nhiệm vụ từ thành phần điều khiển.

3.2.1.2 Giải thuật thêm một thành viên mới vào hệ thống
Một thành viên N muốn gia nhập vào hệ thống thì phải theo những bước như
sau:
Tương tác với thành phần điều khiển C.
Thành phần điều khiển C sẽ gửi những thông tin về hệ thống hiện tại cho N,

đồng thời cũng yêu cầu N liên kết tạm vào một thành viên nào đó trong hệ thống.
N sau khi liên ếkt tạm vào hệ thống, nó sẽ gửi thông điệp ping tới tất cả
những peer sẵn có trong hệ thống và đợi thơng điệp trả về.
N sẽ gửi những thông tin này đến thành phần điều khiển. Dựa vào những
thông tin nhận được, thành phần điều khiển sẽ quyết định vị trí gia nhập của thành
viên mới.

(a) N yêu cầu gia nhập và nhận những chỉ dẫn từ peer điều khiển

15


(b) N khảo sát những node hiện có và gửi kết quả đển node điều khiển

(c) N được yêu cầu để làm con của C và cha của D
Hình 3.1: Một peer tham gia vào hệ thống dùng giải thuật ALMI

3.2.1.3 Cách duy trì cây
Mỗi peer gửi thơng tin cập nhập đến peer điều khiển theo định kỳ. Những
thông tin có thể bao gồm thơng tin giám sát của những thành viên khác trong hệ
thống. Dựa vào những thông tin nhận được thành phần điều khiển sẽ tính tốn lại
minimum spanning tree và có thể yêu cầu một thành viên chuyển sang cha khác.
Một thành viên muốn rời khỏi hệ thống nó chỉ cần gửi thơng điệp LEAVE
đến những thành viên cha và con của nó nếu có. Trong trường nếu nó có con, thì
những thành viên con này sẽ gửi thông điệp REJOIN đến thành phần điều khiển để
gia nhập lại.
16


Trong trường hợp vì một lý do nào đó, một thành phần chết mà khơng gửi

thơng điệp LEAVE thì thành viên cha và những thành viên con của nó nếu có sẽ tự
động phát hiện ra sau một thời gian không thể liên lạc. Trong trường hợp này
thành viên cha sẽ xóa thành viên này từ danh sách con của nó, trong khi đó những
thành viên con sẽ gửi lại thông điệp REJOIN đến thành viên điều khiển.

3.2.1.4 Cách truyền dữ liệu trong hệ thống
Dữ liệu được truyền dọc theo cây multicast. Khái niệm cha con trong cây
khơng có ý nghĩa tron g chiều truyền dữ liệu. Dữ liệu có thể truyền từ con đến cha
và ngược lại. Dữ liệu được truyền giữa hai thành viên dựa theo cơ chế unicast và
có hai giao thức được dùng để truyền dữ liệu: UDP và TCP. Tùy thuộc vào ứng
dụng mà chúng ta chọn giao thức truyền dữ liệu thích hợp.

3.2.1.5 Một số đặc điểm của ALMI
Với giải thuật thêm một thành viên mới vào hệ thống này, trong thời gian
một thành viên mới tham gia vào hệ thống nó khơng ảnh hưởng tới cấu trúc của
cây.
Có thể dùng TCP để truyền dữ liệu, điều này tăng độ tin cậy.
Tuy nhiên với phương pháp này chúng ta sẽ gặp khó khăn trong việc mở
rộng, nó dễ dẫn đến hiện tượng thắt nút cổ chai đối với peer điều khiển.

3.2.2 CAN
3.2.2.1 Giới thiệu
CAN [2] multicast là một lớp ALM của CAN. Việc quản lý những peer trong
hệ thống dựa vào kỹ thuật bảng băm phân tán giống như kỹ thuật Pastry, nó ánh xạ
peerId và khóa của đối tượng vào một khơng gian địa chỉ. Mỗi peer trong CAN
tương ứng với một không gian địa chỉ.
Mỗi peer trong CAN duy trì m
ột bảng định tuyến tọa độ là những peer kế
cận của nó trong không gian tọa độ. Hai peer là hai kế cận của nhau nếu tọa độ của
nó có d -1 chiều tọa độ nằm dọc theo nhau và có một tọa độ bằng nhau.


3.2.2.2 Giải thuật một peer tham gia vào CAN
Một peer muốn tham gia vào hệ thống thì đầu tiên nó phải chọn một tọa độ
ngẫu nhiên và liên ạl c được với máy bootstrap, đây là một máy được hiện thực
riêng dựa trên giải thuật Pastry hay một giải thuật tương đương. Chi tiết về máy
bootstrap không được bàn kỹ trong tài liệu này. Khi peer mới liên lạc với máy
bootstrap nó sẽ nhận được thơng tin của một vài peer có sẵn trong hệ thống. Dựa
vào những peer có sẵn trong hệ thống này nó sẽ truyền thơng điệp gia nhập đến
đúng tọa độ nó mong muốn ban đầu. Tại vị trí này, có một peer đang tồn tại sẵn vì
vậy nó sẽ thực hiện chia đôi peer tại tọa độ này.
17


Hình 3.2: Một peer tham gia vào hệ thống dùng CAN

3.2.2.3 Cách duy trì các peer trong CAN
Các peer trong CAN sẽ gửi thông điệp UPDATE theo định kỳ đến tất cả
những peer kế cận của nó. Nội dung của thơng điệp bao gồm: tọa độ của nó, danh
sách và tọa độ của những peer kế cận.
Một peer không nhận được thơng điệp UPDATE từ những peer kế cận của
nó theo định kỳ thì nó xem như peer kế cận của nó đã chết vì vậy nó khởi tạo một
timer để điều khiển việc này. Chi tiết sẽ được trình bày t rong phần một peer rời
khỏi hệ thống.
Một peer muốn rời khỏi hệ thống bằng cách gửi thông điệp LEAVE đến
những peer kế cận của nó. Mỗi peer nhận được thơng điệp LEAVE từ peer kế cận
của nó, nó sẽ cập nhập lại danh sách những peer kế cận của nó, đồng thời nó cũng
khởi tạo timer để điều khiển việc này. Nếu thời gian định thời của một peer kế cận
nào đó kết thúc trước những peer cịn lại thì nó gửi thơng điệp đến tất cả những
peer này về tọa độ của nó, nếu peer nào có tọa độ nhỏ hơn sẽ gửi thông báo lại với
những peer kế cận của peer rời khỏi hệ thống. Tọa độ của peer rời khỏi hệ thống sẽ

được nối với peer kế cận có tọa độ nhỏ nhất.
18


3.2.2.4 Cách truyền dữ liệu trong CAN
Thông điệp được truyền trong CAN như sau:
Peer nguồn sẽ gửi thông điệp đến tất cả peer kế cận của nó.
Một peer mà nhận dữ liệu dọc theo chiều thứ i thì nó sẽ gửi dữ liệu này đến
tất cả các chiều từ 1 đến i-1. Ngồi ra nó cũng gửi dữ liệu theo chiều thứ i nhưng
về phía đối diện với nơi nó nhận dữ liệu.
Để tránh sự trùng lặp dữ liệu thì mỗi peer nó lưu lại một số lượng dữ liệu nào
mà nó đã nhận và gửi đi. Vì vậy lần sau nếu nhận dữ liệu này nó sẽ khơng phải gửi
đi.

Hình 3.3: Truyền dữ liệu dùng giải thuật CAN

3.2.2.5 Đặc điểm
CAN rất dễ để mở rộng.
Việc định tuyến trong CAN dựa vào giải thuật tham lam và kỹ thuật DHT vì
vậy nó bảo đảm mỗi peer trong hệ thống biết được một peer bị chết. Tuy nhiên đây
cũng là điểm yếu trong CAN, với đặc điểm này dễ gây ra hiện tượng tắt nghẽn.
Với việc dùng máy bootstrap không thật sự đem lại hiệu quả trong CAN, vì
vậy tương lai việc chọn một peer ngẫu nhiên sẽ thay thế máy bootstrap.

19


3.2.3 HMTP (Host Multicast Tree Protocol)
3.2.3.1 Giới thiệu
HMTP [4] thì tương tự với Yoid, tuy nhiên việc xây dựng cây dựa vào những

ràng buộc về chi phí và được tối ưu về thời gian trễ.
Trong thiết kế của HMTP, hệ thống ln ln có một thành viên đặc biệt,
thành viên này không tham gia vào vi
ệc tru yền dữ liệu, nó chứa những thơng tin
cập nhập của peer gốc trong cây. Ngồi ra, nó cịn có nhiệm vụ quan trọng trong
việc xây dựng cây. Mọi thành viên muốn gia nhập vào hệ thống thì phải thơng qua
thành viên này. Thành viên này được gọi là HMRP (Host Multicast Rendevous
Point).
Mỗi thành viên trong nhóm của HMTP có thể là gốc của một cây con hay
cũng có thể là gốc của một cây IP Multicast.
Giữa hai thành viên được kết nối với nhau bằng một unicast tunnel.

Hình 3.4: Kiến trúc của HMTP

20


3.2.3.2 Giải thuật một thành viên gia nhập vào hệ thống
Một thành viên muốn gia nhập vào hệ thống thì cần có những bước sau:
N phải gửi yêu cầu đến peer gốc R này để xin được làm peer con.
Nếu R chấp nhận N như là con mới thì việc gia nhập thành công; ngược lại
nếu R không chấp nhận N là con thì R sẽ gửi danh sách các con của nó cho N.
N gửi thơng điệp ping đến những con này để tìm ra peer gần nó nhất. Sau đó
nó gửi thơng điệp xin được làm con đến peer này.
Việc này sẽ được lập lại cho đến khi N tìm được cha. Có nghĩa là việc gia
nhập thành cơng.

3.2.3.3 Cách duy trì những thành viên trong nhóm
Mỗi peer con gửi thơng điệp REFRESH đến cha của nó theo định kỳ. Trong
khi những peer cha sẽ gửi lại cho những peer con thơng điệp PATH mà nó có chứa

thơng tin về đường đi từ peer gốc đến nó hiện tại.
Peer gốc phải gửi thông điệp REFRESH đến HMRP peer để HMRP có thể
cập nhật thơng tin của peer gốc hiện tại.
Mỗi peer lưu những thông tin về danh sách con của nó và đồng thời chứa
thơng tin về đường đi từ peer gốc đến nó.
Một thành viên rời nhóm nó phải thơng báo cho peer cha và con của nó nếu
có ngoại trừ trường hợp peer này chết đột ngột.
Peer cha nhận được thông điệp LEAVE từ peer con nó sẽ xóa peer con này
trong danh sách con của nó.
Peer con nhận được thơng điệp LEAVE từ peer cha nó sẽ tìm cha mới dựa
vào giải thuật gia nhập lại. Giải thuật này dựa vào thông tin đường đi từ peer gốc
đến nó để tìm cha mới.

3.2.3.4 Cách truyền dữ liệu
Một thành viên khi nhận dữ liệu từ peer khác nó sẽ chuyển cho những thành
viên con của nó nếu có. Với đặc điểm thiết kế của HMTP, việc truyền dữ liệu có
thể dựa vào IP multicast, LAN hay truyền theo kiểu unicast giữa những thành viên
trong cây.

3.2.3.5 Đặc điểm
Việc gia nhập của một thành viên mới nó chỉ dựa vào những thành viên cục
bộ, có nghĩa là dựa vào thông tin của một peer gốc hay con của nó theo đệ qui cho
đến khi tìm được cha. Vì vậy HMTP dễ để mở rộng.
Giảm số lượng thông điệp cập nhập định kỳ bởi vì chỉ có sự cập nhập nội bộ
giữa cha và con.
21


Tuy nhiên thứ tự gia nhập vào nhóm sẽ ảnh hưởng tới chất lượng của cây,
như trong trường hợp một peer ở gần peer gốc nhưng vì gia nhập sau nên peer này

có thể trở thành con rất xa với peer gốc.

3.2.4 NICE
3.2.4.1 Giới thiệu
Những peer trong NICE [6] được sắp xếp theo cơ chế phân tầng. Mỗi tầng có
một tập các cluster. Mỗi cluster giống như một nhóm peer, một trong những peer
này sẽ được cử làm lãnh đạo. Những kết nối thì được thiết lập ngay trong giai
đoạn xây dựng cây vì vậy việc truyền dữ liệu sẽ dựa vào những đường cụ thể này
mà khơng cần tính tốn lại đường đi.
Trong thiết kế của NICE có một peer đặc biệt không tham gia vào truyền dữ
liệu nhưng nó có vai trị rất quan trọng trong việc xây dựng cây NICE. Mọi thành
viên muốn gia nhập vào cây NICE phải thơng qua peer này, đó là peer HMRP.
Việc xây dựng cluster và lớp cho NICE dựa vào những tiêu chí như sau:
Tại mỗi lớp một peer chỉ thuộc một cluster.
Nếu một peer có mặt ở lớp Li thì nó phải có mặt ở lớp Li-1.
Nếu một peer khơng có mặt ở lớp Li thì nó khơng có mặt ở lớp Li-1.
Mỗi cluster có kích thước từ k đến 3k-1, trong đó k là ộmt hằng số thực
nghiệm do chúng ta qui định. Peer lãnh đạo của cluster nên là peer nằm giữa của
cluster đó.

Hình 3.5: Kiến trúc của NICE

3.2.4.2 Giải thuật gia nhập một thành viên mới
Một thành viên mới gia nhập vào cây NICE nó phải nằm ở lớp 0. Vì vậy,
một thành viên N muốn gia nhập vào cây NICE phải thông qua những bước như
sau:
22


N phải giao tiếp với HMRP peer để lấy thông tin về peer M ở lớp cao nhất

trong cây.
N yêu cầu M gửi cho nó thơng tin những con của M. Dựa vào thơng tin con
của M, N sẽ tìm ra được N gần với peer con M1 của M nào gần nhất. Nếu M1 nằm
ở lớp lớn hơn 0, thì N tiếp tục u cầu thơng tin con của M1 để tìm peer gần nó
nhất. Việc này được lặp lại cho đến khi N gia nhập vào cây ở lớp 0.

Hình 3.6: Một peer tham gia vào hệ thống dùng NICE

23


3.2.4.3 Cách duy trì và giải thuật một thành viên rời khỏi nhóm
Mỗi thành viên H trong cluster C gửi thông điệp Heartbeat đến cluster leader
theo định kỳ. Nội dung của thông điệp chứa thông tin về khoảng cách từ H đến
những peer còn lại trong cluster C này.
Khi một peer H muốn rời khỏi nhóm nó chỉ cần gửi thông điệp LEAVE đến
tất cả các thành viên trong những cluster mà nó đã từng tham gia vào.
Trong kiến trúc của NICE chúng ta cần quan tâm tới số lượng phần tử trong
một cluster phải vì vậy theo định kỳ mỗi peer lãnh đạo của cluster phải kiểm tra
kích thước cluster của nó. Nếu kích thước lớn hơn 3k – 1 thì nó sẽ u cầu để tách
cluster này thành hai cluster con. Ngược lại nếu kích thước của cluster nhỏ hơn k
thì nó u cầu sát nhập với một cluster kế cận nào đó.

3.2.4.4 Cách truyền dữ liệu trong NICE

Hình 3.7: Truyền dữ liệu dùng giải thuật NICE

3.2.4.5 Đặc điểm
Việc thêm một thành viên mới vào cây chỉ dựa vào thơng tin nội bộ của một
cluster vì vậy NICE rất dễ để mở rộng và việc xây dựng cây rất nhanh.


3.2.5 Scribe/Pastry
Scribe [9] là một lớp ALM mà nó chạy dựa vào Pastry giải thuật, Pastry là
nền tảng định tuyến cho việc phân tán số lượng lớn đối tượng trong mạng P2P. Có
2 thuộc tính chính và cũng là thuộc tính nền tảng cho Scribe là: khả năng mở rộng
và độ ổn định.

24


3.2.5.1 Pastry protocol
Pastry [9] hiện thực một bảng băm phân tán mà mỗi phần tử của nó là một
cặp ánh xạ giữa những peer và key. Để đạt được khả n ăng mở rộng, Pastry đã
phân tán những đối tượng đồng dạng thơng qua tất cả các peer trong nhóm. Pastry
hoạt động như sau:
Mỗi Pastry peer được gán một ID ngẫu nhiên và là duy nhất, giá trị này được
lựa chọn từ 0 đến – 1.
Mỗi Pastry peer có một bảng đị nh tuyến mà nó chứa ánh xạ giữa ID của
những peer khác trong hệ thống và địa chỉ IP của những peer này. Tuy nhiên để
bảo đảm khả năng mở rộng bảng định tuyến được xây dựng một cách chiến lược
như sau: một peer sẽ biết những peer mà có một số lượng số đầu t iên trong ID
trùng với ID của nó. Chúng ta cũng có thể hiểu điều này như sau: một peer sẽ chứa
danh sách của những peer có ID gần giống với nó và một danh sách của những
peer có ID khác. Việc so sách được thực hiện với 16 số đầu tiên. Vì vậy một peer
có ID là 0x65a1… sẽ có trong bảng định tuyến như hình sau.

Hình 3.8: Bảng định tuyến Pastry cho peer với ID 0x65a1…
Việc tìm đường đi trong Pastry là một cấu trúc phân cấp. Ví dụ peer A muốn
gửi thơng điếp đến peer ID là 0xd46a1d thì nó ẽs gửi đến peer trong bảng định
tuyến của nó với B là peer gần nhất với ID của đích, trong trường hợp này là B.


25