Đại Học Quốc Gia Thành Phố Hồ Chí Minh
Trường Đại Học Bách Khoa

NGUYỄN ANH TÚ

XÂY DỰNG GIẢI THUẬT PHÂN BỐ
DỮ LIỆU TRÊN MẠNG INTERNET
Chuyên ngành: Khoa học Máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 11 năm 2007



ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
Độc Lập - Tự Do - Hạnh Phúc
------------------oOo--Tp. HCM, ngày . .05. . tháng . .11. . năm .2007.

NHIỆM VỤ LUẬN VĂN THẠC SĨ

Họ và tên học viên : Nguyễn Anh Tú
Giới tính : Nam / Nữ
Ngày, tháng, năm sinh : 22/05/1979
Nơi sinh : Bình Định................
Chun ngành : Khoa học Máy tính.......................................................................................
Khố : 2005..........................................................................................................................
1- TÊN ĐỀ TÀI : ................................................................................................................
XÂY DỰNG GIẢI THUẬT PHÂN BỐ DỮ LIỆU TRÊN MẠNG INTERNET .............
...........................................................................................................................................

...........................................................................................................................................
2- NHIỆM VỤ LUẬN VĂN : ..............................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................
3- NGÀY GIAO NHIỆM VỤ : ............................................................................................
4- NGÀY HOÀN THÀNH NHIỆM VỤ :...........................................................................
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Thoại Nam...............................................
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

TS. Thoại Nam

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

TS. Đinh Đức Anh Vũ


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học : TS. Thoại Nam.............................................................

Cán bộ chấm nhận xét 1 :.............................................................................................


Cán bộ chấm nhận xét 2 :.............................................................................................

Luận văn thạc sĩ được bảo vệ tại
HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . tháng . . . . năm . 2007 .


LỜI CAM ĐOAN
Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác như đã ghi rõ
trong luận văn, các cơng việc trình bày trong luận văn này là do chính tơi thực hiện và chưa
có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này hoặc
trường khác.
Ngày 05 tháng 11 năm 2007
Nguyễn Anh Tú


LỜI CẢM ƠN
Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến TS. Thoại Nam, người Thầy đã tận
tình hướng dẫn tơi trong suốt q trình từ đại học tới cao học và tạo mọi điều kiện để tơi có
thể hồn thành luận văn này.
Tơi cũng xin cảm ơn gia đình đã động viên và tạo mọi điều kiện tốt nhất để tơi có thể tiếp tục
theo đuổi việc học tập nghiên cứu. Tôi trân trọng dành tặng thành quả của luận văn này cho
Cha Mẹ. Nhờ công lao dưỡng dục của Người mà chúng con mới có được thành quả như ngày
hơm nay. Con xin hứa sẽ tiếp tục cố gắng phấn đấu để vươn cao hơn nữa.


MỤC LỤC
Chương 1:
GIỚI THIỆU.................................................................................................................................................. 1
1. Đặt Vấn Đề................................................................................................................................................ 1

2. Các Giải Pháp Hiện Hữu ........................................................................................................................... 2
2.1
Server-Based Solution ................................................................................................................... 2
2.2
Complete-Graph-Based Solution................................................................................................... 3
2.3
Tree/Mesh Multicast Solution ....................................................................................................... 3
3. Sơ Lược Về Giải Pháp............................................................................................................................... 3
4. Kết Quả...................................................................................................................................................... 5
Chương 2:
TỔNG QUAN VÀ CÁC GIẢI PHÁP LIÊN QUAN .................................................................................... 7
1. Multicast Protocols................................................................................................................................ 7
1.1 Nice ..................................................................................................................................................... 7
1.2 Narada ............................................................................................................................................... 10
1.3 PRISM ............................................................................................................................................... 14
1.4 Yoid................................................................................................................................................... 14
1.5 ALMI................................................................................................................................................. 17
1.6 Host Multicast Tree Protocol............................................................................................................. 18
2. Kết Luận .............................................................................................................................................. 20
Chương 3:
SOLUTION: DYNAMIC NETWORK CONDITION ADAPTING MULTI-SOURCE MULTICAST
PROTOCOL................................................................................................................................................ 22
1. Đặt Vấn Đề.......................................................................................................................................... 22
2. Giải pháp ............................................................................................................................................. 22
2.1 Mesh Building ................................................................................................................................... 22
2.2 Data Routing...................................................................................................................................... 22
2.2.1 Overview .................................................................................................................................... 22
2.2.2 Routing Version.......................................................................................................................... 24
2.2.3 Routing Table Organization ....................................................................................................... 24
2.2.4 Routing Algorithm...................................................................................................................... 27

2.3 Single-Source Multicast Protocol...................................................................................................... 28
2.3.1 Message Types ........................................................................................................................... 28
2.3.2 Data Structures ........................................................................................................................... 29
2.3.3 State Machine Diagram .............................................................................................................. 31
2.3.4 Activity Diagrams ...................................................................................................................... 31
2.4 Multi-Source Multicast Protocol ....................................................................................................... 36
2.4.1 Congested Detection................................................................................................................... 37
2.4.1.1 Overview ............................................................................................................................. 37
2.4.1.2 Congestion Types ................................................................................................................ 37
2.4.1.3 Message Types .................................................................................................................... 37
2.4.1.4 Data Structures .................................................................................................................... 38
2.4.1.5 Congestion Level Control.................................................................................................... 41
2.4.1.6 End Point Relaxation........................................................................................................... 41
2.4.1.7 Congestion Detecting Algorithm......................................................................................... 41
a. Required Supports from TCP Layer.................................................................................... 41
b. Configuration Variables ...................................................................................................... 42
c. Message Queue Congestion Threshold ............................................................................... 42
d. Message Queue Congestion Threshold Delta...................................................................... 42
e. Average Value of Sending Duartion ................................................................................... 42
f. Average Value of Receiving Duration ................................................................................ 42


g. Average Value of ACK Duration ........................................................................................ 42
h. The Algorithm ..................................................................................................................... 43
2.4.2 Network Condition Adaption ..................................................................................................... 50
2.4.2.1 Overview ............................................................................................................................. 50
2.4.2.2 Message Types .................................................................................................................... 50
2.4.2.3 Data Structures .................................................................................................................... 51
2.4.2.4 Parent Changing Protocol.................................................................................................... 52
Chương 4:

MÔ PHỎNG ĐÁNH GIÁ ........................................................................................................................... 62
1. Test Case 1 .............................................................................................................................................. 62
2. Test Case 2 .............................................................................................................................................. 63
3. Test Case 3 .............................................................................................................................................. 64
4. Test Case 4 .............................................................................................................................................. 65
5. Test Case 5 .............................................................................................................................................. 67
6. Test Case 6 .............................................................................................................................................. 68
7. Test Case 7 .............................................................................................................................................. 69
8. Test Case 8 .............................................................................................................................................. 70
9. Test Case 9 .............................................................................................................................................. 71
10. Test Case 10 .......................................................................................................................................... 73
11. Test Case 11 .......................................................................................................................................... 74
KẾT LUẬN ................................................................................................................................................. 76
THAM KHẢO............................................................................................................................................. 77
Phụ Lục Chương 3:
SOLUTION: DYNAMIC NETWORK CONDITION ADAPTING MULTI-SOURCE MULTICAST
PROTOCOL................................................................................................................................................ 78
1. Mesh Building ..................................................................................................................................... 78
1.1 Node Management ............................................................................................................................ 78
1.1.1 Overview .................................................................................................................................... 78
1.1.2 Message Types ........................................................................................................................... 78
1.1.3 Data Structures ........................................................................................................................... 79
1.1.4 Ping Protocol .............................................................................................................................. 80
1.1.5 Group Joining Protocol............................................................................................................... 83
1.1.6 Group Leaving Protocol ............................................................................................................. 83
1.1.7 Died Node Detection .................................................................................................................. 83
1.2 Neighbor Management ...................................................................................................................... 84
1.2.1 Overview .................................................................................................................................... 84
1.2.2 Message Types ........................................................................................................................... 84
1.2.3 Data Structures ........................................................................................................................... 85

1.2.4 Neighbor Adding Protocol ......................................................................................................... 86
1.2.5 Neighbor Removing Protocol..................................................................................................... 88
1.2.6 Neighbors List Improvement...................................................................................................... 91
1.2.7 Ping Protocol .............................................................................................................................. 92
2. Single-Source Multicast Protocol........................................................................................................ 93
2.1 Broadcast Cancellation...................................................................................................................... 93
2.2 Neighbor Removing .......................................................................................................................... 93
3. Multi-Source Multicast Protocol ......................................................................................................... 95
3.1 Converged Detection......................................................................................................................... 95
3.1.1 Data Structures ........................................................................................................................... 95
3.1.2 Message Types ........................................................................................................................... 96
3.1.3 Configuration Variables ............................................................................................................. 96
3.1.4 The Algorithm ............................................................................................................................ 97
3.2 Mesh Refinement .............................................................................................................................. 99


3.3 Died Node Processing ....................................................................................................................... 99
Phụ Lục Môi Trường Mô Phỏng:
Network Simulator .................................................................................................................................... 101
1. Overview ............................................................................................................................................... 101
2. Examples ............................................................................................................................................... 101
2.1
OTcl Script ................................................................................................................................ 101
2.2
C++ Code .................................................................................................................................. 102
Phụ Lục Thuật Ngữ:
CÁC THUẬT NGỮ .................................................................................................................................. 104
1. ALM .................................................................................................................................................. 104
2. BOM.................................................................................................................................................. 104
3. Broadcast ........................................................................................................................................... 104

4. Broadcast Message ............................................................................................................................ 104
5. Control Message................................................................................................................................ 104
6. Current Node ..................................................................................................................................... 104
7. Data Message .................................................................................................................................... 104
8. DPC ................................................................................................................................................... 104
9. End Point ........................................................................................................................................... 104
10. FCP.................................................................................................................................................. 104
11. Joined Node..................................................................................................................................... 104
12. Left Node......................................................................................................................................... 104
13. List Structure ................................................................................................................................... 105
14. Map structure................................................................................................................................... 105
15. Member Node.................................................................................................................................. 105
16. SSMP............................................................................................................................................... 105
17. Multicast.......................................................................................................................................... 105
18. Multicast Tree.................................................................................................................................. 105
19. Node ................................................................................................................................................ 105
20. Overlay Link.................................................................................................................................... 105
21. Peer Node ........................................................................................................................................ 105
22. Protocol Message ............................................................................................................................ 105
23. Rendezvous Point (RP).................................................................................................................... 105
24. Source Node .................................................................................................................................... 105
25. MSMP ............................................................................................................................................. 105
26. VCA................................................................................................................................................. 106


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

CHƯƠNG 1

GIỚI THIỆU

1. Đặt Vấn Đề
Với sự phát triển của công nghệ ngày nay, tốc độ của đường truyền dữ liệu ngày càng được nâng cao.
Điều này làm cho chi phí truyền dữ liệu qua internet ngày càng giảm và ý tưởng hội nghị từ xa (video
conference) trở nên khả thi ngày càng cao cho các tổ chức, doanh nghiệp có nhu cầu hội họp trong điều
kiện cách trở về mặt địa lý. Hội nghị từ xa có ưu thế tiết kiệm về mặt thời gian và tiền bạc do chi phí đi lại
so với kiểu hội nghi truyền thống.
Với xu thế này, hướng đề tài sẽ đi vào việc nghiên cứu một giải thuật phân bố dữ liệu trên internet đặc thù
cho các ứng dụng video conference.
Có ba hướng chính trong việc xây dựng các ứng dụng video conference. Hướng thứ nhất dựa trên nền IP
multicast, một thành phần trong cơ sở hạ tầng TCP/IP. Hướng tiếp cận có ưu điểm là đã có sẳn một
multicast protocol và protocol này chạy rất hiệu quả, ít chiếm băng thơng (trong mạng LAN, router chỉ
cần gửi một gói dữ liệu là đủ để thực hiện lệnh multicast đến một nhóm các computer trong mạng).
Nhưng nó lại có một số hạn chế như sau: 1) IP multicast cần sự hỗ trợ từ phía hệ điều hành (OS), nhưng
hiện nay phần lớn OS đều hỗ trợ chức năng này. 2) Cần sự hỗ trợ cho IP multicast procol ở các router.
Thông thường, hiện nay các router đều có hỗ trợ IP multicast, nhưng tính năng này đơi khi bị các nhà
quản trị mạng tắt đi vì một hay nhiều lý do nào đó. 3) IP multicast có khơng gian địa chỉ nhỏ 27 bit. Vấn
đề này được giải quyết với IPv6. 4) vấn đề bảng routing kích thước lớn ở mỗi router tham gia vào quá
trình multicast. Mỗi router phải duy trì bảng routing cho mỗi nhóm IP multicast. Hướng tiếp cận thứ hai là
Application Layer Multicast (ALM), một hướng không phụ thuộc sự hỗ trợ multicast của cơ sở hạ tầng
mạng và khơng cần sự hỗ trợ về mặt cấu hình từ các nhà quản trị mạng. Hướng này sử dụng unicast để
thực hiện việc multicast dữ liệu, cho nên nó khơng hiệu quả về mặt băng thông so với IP multicast. Hướng
thứ ba là kết hợp giữa IP multicast và ALM. Xem các IP multicast-enabled island như là một host đơn và
sử dụng ALM cho các host này.
Các Video conference Application (VCA) thường là các nhóm multicast có kích thước nhỏ nên việc sử
dụng IP multicast không được hiệu quả lắm vì vấn đề quản lý q nhiều nhóm multicast nhỏ ở các router.
Giải pháp ALM là một lựa chọn khác cho VCA. ALM sử dụng vài member trong nhóm multicast như là
các router, thay thế chức năng của các network router. Các giải pháp ALM không phụ vào sự hỗ trợ của
các network router, giúp VCA để triển khai hơn.
Để ALM là một lựa chọn thay thế đủ tốt cho IP multicast đối với các nhóm nhỏ có nhiều source node
(node phát data) thì một ALM protocol cần phải có một cơ chế tận dụng tốt những node có bandwidth lớn

và sử dụng các node này như là các router node cho nhóm multicast. Nhiệm vụ của các router node này là
nhận data message từ một source node và forward data message này đến các node khác. Số lượng các
node được forward bởi một router node tùy thuộc vào lượng bandwidth dư thừa của chính router node đó.
Như vậy mục tiêu của đề tài này là xây dựng một ALM protocol cho VCA với các đặc tính sau:
- Có nhiều source node.
- Số source node có thể nhỏ hơn tổng số node.
- Các source node có cùng data rate (tốc độ phát data).
- Yêu cầu về delay của data message không được xem xét.

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

1


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

-

Phục vụ cho nhóm multicast có link vật lý có bandwidth khả dụng bất đối xứng hoặc có link đối
xứng và số source node nhỏ hơn tổng số node trong nhóm multicast.
Tìm một multicast tree cho mỗi source node sao cho đáp ứng được yêu cầu về data rate mà khơng
gây nghẽn. Khơng cố gắng tìm lời giải tốt nhất.
Khả năng thích ứng với điều kiện thay đổi động của network. Tự động thay đổi các multicast tree
để thích ứng với điều kiện network mới.
Thời gian hội tụ về lời giải khả dụng đủ nhanh.
Phục vụ cho nhóm multicast có kích thước nhỏ.
Dựa trên nền TCP/IP.

Như vậy bài tốn mà đề tài này đặt ra như sau:
- Input: cho trước một nhóm multicast có m member node và n source node (node phát) có data rate

Dr kbps , n ≤ m. Network Topology và bandwidth đường truyền giữa các member node không
được biết trước.
- Output: bảng routing tại mỗi member node. Tổng hợp các bảng routing này lại sẽ có được
multicast tree cho mỗi source node.

2. Các Giải Pháp Hiện Hữu
Chỉ đề cập đến các giải pháp không phụ thuộc nhà cung cấp hạ tầng network. IP Multicast and Satellite
Multicast là các giải pháp phụ thuộc nhà cung cấp hạ tầng network.

2.1 Server-Based Solution
Có một server đóng vai trị như một router (server này được gọi là reflector), nhận data message từ
member node và forward message này đến các member node khác. Có thể có nhiều reflector phối hợp
cùng nhau và mỗi member node (participant) chỉ kết nối đến một reflector.
Giải pháp này sử dụng bandwidth tại mỗi member node ở mức tối thiểu, nhưng sử dụng rất nhiều
bandwidth tại mỗi reflector.
Participant

Participant

Reflector

Participant

Participant

Hình 1.1

Reflector có thể hoặc combine các video stream từ các participant thành một stream đơn rồi gửi đến các
participant cịn lại (cách làm này sử dụng ít bandwidth) hoặc để nguyên stream gốc và chỉ forward đến các
participant còn lại.


Dynamic Network Condition Adapting Multi-Source Multicast Protocol

2


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

2.2 Complete-Graph-Based Solution
Xem mỗi kết nối giữa hai member node là một cạnh, thì graph được hình thành từ tập các node của nhóm
multicast là một complete graph. Đây là giải pháp đơn giản nhất và chỉ phù hợp với nhóm multicast có số
source node bằng số member node và các link vật lý của mỗi node có bandwidth khả dụng đối xứng hoặc
vấn đề tối ưu bandwidth là không quan trọng.

Hình 1.2

2.3 Tree/Mesh Multicast Solution
Các multicast protocol như Narada, Nice, ALMI, HMTP đều có thể sử dụng cho VCA. Trong đó Narada
tập trung cho việc tối ưu latency cho data message, nhưng chưa tập trung cho việc tối ưu bandwidth, xử lý
hiện tượng multicast mesh không đáp ứng được data rate yêu cầu. Các protocol còn lại dựa chủ yếu vào
một cấu trúc cây dùng chung để multicast, cách làm này không thực sự hiệu quả cho multicast với nhiều
source node và gây ra delay lớn khi source node ở vị trí node lá. Và vấn đề tối ưu bandwidth cũng như
Narada, chưa giải quyết tốt.

3. Sơ Lược Về Giải Pháp
Các node trong nhóm multicast được tổ chức thành một mesh. Mỗi source node sử dụng một multicast
tree riêng biệt để multicast data message đến các node còn lại trong nhóm multicast. Mỗi cạnh của
multicast tree là một cạnh của cấu trúc mesh.
1


1

2

2

3
4

3
4

Hình 1.3

Hình 1.4

Hình 1.3, 1.4, 1.5, 1.6 trình bày cấu trúc mesh và các multicast tree của một nhóm multicast gồm 4 node
và các node này đều là source node.

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

3


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

1

1


2

2

3
4

3
4

Hình 1.5

Hình 1.6

Quá trình hình thành multicast tree cho mỗi source node gồm hai giai đoạn:
- Broadcast trên mesh (BOM) để xây dựng các multicast tree ban đầu. Các multicast tree này chưa
là các multicast tree cuối cùng.
- Dùng cơ chế phát hiện, xử lý nghẽn (DPC) để chỉnh sửa dần các multicast tree ban đầu. Quá trình
chỉnh sửa này sẽ dừng lại khi các multicast tree thỏa mãn yêu cầu của bài toán.
BOM được chạy đầu tiên để tạo ra các multicast tree khởi đầu cho các source node. Sau đó các source
node bắt đầu phát data. DPC giám sát quá trình lan truyền data message trên mỗi multicast tree. Khi có
hiện tượng nghẽn tại một member node nào đó, DPC tiến hành xử lý, chọn một multicast tree và thay đổi
cấu trúc của nó dựa trên các thơng tin routing đã thu thập được bởi BOM. Quá trình xử lý của DPC có tinh
chất lặp đi, lặp lại đến khi nào hết nghẽn thì dừng lại. Khi DPC nhận thấy rằng thông tin routing được thu
thập bởi BOM ở lần chạy trước chưa đủ để protocol hội tụ, nó kích hoạt BOM chạy lại để thu thập lại
thơng tin routing mới đầy đủ hơn.
BOM hoạt động theo cơ chế sau: source node gửi broadcast message đến các neighbor, các neighbor của
source node đến lượt mình forward broadcast message vừa nhận được đến các neighbor của nó ngoại trừ
neighbor mà nó vừa nhận broadcast message. Q trình này cứ thế diễn ra cho đến khi tất cả các node đều
đã nhận được broadcast message. mỗi node trên mesh lưu thơng tin về các neighbor mà nó nhận hoặc gửi

broadcast message. Hình 1.7 trình bày cơ chế hoạt động này. Node 0 là node phát data. Các cạnh màu đỏ
chỉ multicast tree kết quả. Các mũi tên màu đỏ chỉ hướng các broadcast message được gửi bởi node đang
xét.

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

4


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

5

4

9

0

1

3

8

2

6

7


Hình 1.7
Nội dung chỉ tiết của giải pháp này sẽ được trình bày ở chương 3.

4. Kết Quả
Đã xây dựng được protocol sử dụng và cân đối hiệu quả bandwidth của các member node. Hầu như đưa
các nhóm multicast hội tụ với data rate xấp xỉ giá trị lớn nhất mà nhóm multicast có thể hoạt động khơng
có nghẽn. Trong một số trường hợp kết quả thu được không là lời giải tốt nhất, mà chỉ đủ tốt để không gây
ra nghẽn.

Node
Count
4
5
6
7
8
9
10

Bandwidth (BW) Description
X/Y : Recv BW = X units, Send BW = Y units
Node
0
2
3
4
BW
1/3
1/3

7/3
3/3
Node
0
2
3
4
5
BW
2/4
6/4
1/4
4/4
7/4
Node
0
2
3
4
5
6
BW
3/5
1/5
5/5
6/5
7/5
8/5
Node
0

2
3
4
5
6
7
BW
3/6
5/6
1/6
2/6
4/6
10/6
17/6
Node
0
2
3
4
5
6
7
8
BW
3/7
5/7
1/7
2/7
4/7 13/7 17/7 11/7
Node 0

2
3
4
5
6
7
8
9
BW 3/8 5/8 1/8 2/8 4/8 13/8 17/8 11/8 16/8
Node 0
2
3
4
5
6
7
8
9
10
BW 3/9 5/9 1/9 2/9 4/9 13/9 15/9 11/9 16/9 20/9

Converge
Time
24s
37s
44s
46s
69s
49s
54s


Hình 1.8

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

5


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

Hình 1.8 trình bày bảng kết quả thử nghiệm với các nhóm multicast (network topology như trong hình
1.9) có từ 4 đến 10 member và tất cả các member đều là source node. Tốc độ phát data của tất các member
node như nhau và có giá trị là 1 unit.

0

2

Internet

n

3
Hình 1.9

Các thông số cụ thể (đã bao gồm overhead bandwidth: TCP header, protocol header and control message
của TCP và protocol) của nhóm có 10 member như sau:
Data rate = 833.6 kbps. Node bandwidth in Mbps

10


Node

0

2

3

4

5

6

7

8

9

10

BW 3.5/8.6 5.3/8.8 1.6/8.5 2.6/8.6 4.4/8.7 12.7/9.3 14.6/9.4 10.9/9.1 15.6/9.5 19.6/9.8
Hình 1.20

Theo hình 1.20 ta thấy node 3 chỉ có khả năng up tối đa 1.6 Mbps. Nếu chúng ta dùng complete graph
based solution, thì data rate tối đa mà nhóm multicast này có thể đáp ứng được là 1.6/9 = 0.177 Mbps (giá
trị này chưa tính đến lượng overhead). Điều này giải thích lí do vì sao chúng ta cần một giải thuật
multicast mới như protocol này.


Dynamic Network Condition Adapting Multi-Source Multicast Protocol

6


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

CHƯƠNG 2

TỔNG QUAN VÀ CÁC GIẢI PHÁP LIÊN QUAN

1. Multicast Protocols
1.1 Nice
Nice [1] là một protocol được thiết kế cho các ứng dụng có số lượng lớn các receiver, mục tiêu của
protocol này là nhằm tối ưu chi phí quản lý một số lượng lớn các member. Và tập trung ở các ứng dụng có
bandwith thấp.
Nice quản lý các member theo cơ chế phân cấp, gom các member nằm ở gần nhau vào trong một cluster,
mỗi cluster có số lượng các member nằm trong khoảng từ k đến 3*k – 1. Các cluster được phân nhóm theo
layer. Member đóng vai trò là root của hệ phân cấp này nằm ở layer cao nhất và layer này chỉ có một
member. Tất các member thuộc nhóm multicast (mỗi nhóm multicast có một cây phân cấp) đều nằm ở
layer thấp nhất, layer 0. Mỗi cluster có một member được chọn làm leader, member này phải nằm ở vị trí
trung tâm của cluster. Việc chọn leader ở vị trí trung tâm nhằm mục đích tối ưu hoạt động quản lý và gửi
data đến các member của cluster.
Tập hợp các leader của layer i hình thành nên layer i+1, các member (leader) ở layer i+1 được phân
nhóm thành các cluster của layer i+1. Như vậy một member ở layer i thì nó cũng nằm ở layer j và làm
leader của một cluster mà nó thuộc về trong layer j này với 0≤ jMột member có thể thuộc về nhiều cluster khác nhau. Nhưng ở một layer, thì một member chỉ có thể
thuộc về một cluster.
Nice quản lý các member theo cơ chế phân bố. Leader chịu trách nhiệm quản lý các member trong cluster

của nó. Mỗi member chỉ kết nối trực tiếp đến các member khác trong cùng cluster mà member thuộc về.
Các member trong một cluster định kỳ gửi thông điệp HeartBeat cho nhau nhằm mục đích xác định sự tồn
tại của member trong cluster và tinh chế cây phân cấp. Nếu member gửi HeartBeat là leader thì nội dung
của thơng điệp HeartBeat chứa danh sách các member của cluster. Nếu member gửi HeartBeat khơng là
leader, thì nội dung của thơng điệp chỉ là khoảng cách được ước tính giữa member gửi và member nhận.
Leader cũng định kỳ gửi danh sách các member của cluster thuộc layer trên (layer cao hơn layer hiện thời
1 bậc) mà leader thuộc về, nhằm mục đích để các member của leader join cluster khác cùng layer (tinh chế
cây phân cấp).

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

7


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

Một ví dụ của cây phân cấp
<<abstract>>
Layer
index

Lmax: index of the top most
layer

1..*

contains >>
{index=0 and index in indexes}
1..*

<<host>>
Member
indexes

+member
*
{index=0 and index in indexes}
<< contains

1..*
Cluster Leader is member
of the cluster that it plays
roles as leader.

<<abstract>>
Cluster
index
<< has

1..*
<<abstract>>
0..*
Cluster
index

1..*

+member
contains >>

*

{index and index+1 in indexes}

<<host>>
Cluster Leader

1
+leader

{index>0 and index in indexes}

contains >>
{Layer::index=Cluster::index}

1
<<host>>
Root

{index=Lmax and index in indexes}

1

contains >>

1

<<abstract>>
Layer
index

Sơ đồ tổ chức phân cấp

Mỗi member I định kỳ duyệt danh sách các member của cluster thuộc layer trên mà leader của I thuộc về,
và tìm member J gần nó nhất. Nếu J khác leader của I thì I rời cluster hiện thời và join vào cluster của J
(J làm leader của cluster mới này).

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

8


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

Khi một host Y muốn join vào một nhóm multicast, nó đầu tiên contact đến một host khác được biết trước
gọi là Rendezvous Point (RP) và RP trả về địa chỉ của member X là root của cây phân cấp của nhóm
multicast. Mục tiêu của Y là join vào cluster gần nó nhất thuộc layer 0 của cây phân cấp. Hình vẽ bên dưới
sẽ minh họa chi tiết quá trình join một layer. Trong ngữ cảnh hiện tại thì join layer 0.
Khi một member muốn rời khỏi nhóm multicast, nó gửi thông điệp Remove đến tất cả các cluster mà nó
thuộc về.
Về vấn đề truyền dữ liệu trên cây phân cấp, member đóng vai trị là source của dữ liệu có thể ở bất kỳ vị
trí nào trong cây phân cấp của nhóm multicast. Nhưng nếu member đóng vai trị source này nằm ở vị trí
root thì q trình multicast dữ liệu sẽ tối ưu nhất. Cơ chế multicast dữ liệu như sau: khi một member X
nhận một gói dữ liệu, nó sẽ gửi gói dữ liệu này đến tất cả các peer (các member X có kết nối trực tiếp đến
chúng) của nó ngoại trừ các peer thuộc cùng cluster với peer gửi dữ liệu đến nó.

- Li: index of target layer i needed to join to.
- Lmax : index of the topmost layer.
- CL(i,X): a cluster at layer i and X is also a
member of this cluster.

query RP for the host X in the topmost
layer (the root host of the tree)

i:=Lmax

[ i=Li ]

join CL(i,X)

query host X for the collection Z of its peers at layer
i-1 (members of CL(i-1,X) in which X is a leader)

[ i=Li ]

i:=i-1

find a closest member Y
to X in the collection Z

X:=Y

Các bước của quá trình join một layer

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

9


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

2 ví dụ của cơ chế multicast
Trong 2 hình trên, hình bên trái member phát dữ liệu là A7 và hình bên phải member phát dữ liệu là C0. Ai
thuộc về layer 0, Bi thuộc về layer 1 và 0, C0 thuộc về layer 2, 1, 0 và là leader của chính nó và các Bi.
Tóm lại, Nice có thể được dùng cho các ứng dụng với nhiều member phát dữ liệu. Trong trường hợp xấu
nhất (member phát dữ liệu và member nhận dữ liệu nằm ở 2 bên rìa của cây phân cấp), latency gấp đôi
trường hợp tối ưu (member phát dữ liệu nằm ở root). Tuy nhiên Nice khơng phù hợp cho các ứng dụng có
ràng buộc chặt về latency như video conference. Hơn nữa Nice khơng có cơ chế tận dụng các đường
truyền có băng thơng lớn của member để nâng cao tốc độ multicast chung của cả nhóm multicast. Nice có
một điểm yếu trong việc kháng lỗi, khi một member chết đột ngột thì cây phân cấp sẽ bị phân hoạch và tất
các member mà member nay làm leader sẽ không nhận được dữ liệu gửi tới chúng thơng qua leader này.
Và có một hạn chế nữa về mặt băng thơng là member đóng vai trị là root phải làm leader của n cluster (n
là chỉ số của layer cao nhất), điều này có nghĩa là root trong trường hợp xấu nhất nó phải gửi dữ liệu đến
tất cả các member của n cluster, điều này sẽ hạn chế băng thơng chung của cả nhóm multicast rất nhiều.
1.2 Narada
Narada [2] là một protocol được thiết kế tập trung cho các ứng dụng multicast có số lượng các member
nhỏ và trung bình, khoảng vài trăm member trở lại. Narada tập trung tối ưu giá trị latency của quá trình
multicast dữ liệu với nhiều node phát (multi-source), vì vậy Narada đặc biệt phù hợp cho các ứng dụng có
địi hỏi ràng buộc chặt về latency như video conference, multi-party network game.
Narada sử dụng các member để xây dựng nên một mesh vừa dùng cho chức năng quản lý các member vừa
dùng cho việc truyền dữ liệu. Việc truyền dữ liệu từ node source (node phát dữ liệu) đến các node khác
theo một path dạng tree, có gốc tại node source, và tree này cũng được gọi là reverse shortest path
spanning tree. Mỗi member lưu danh sách của tất cả các member khác trong nhóm multicast. Narada định
kỳ chạy giải thuật distance vector trên mesh để xây dựng nên các reverse shortest path spanning tree cho
mỗi node phát. Và các tree này được thể hiện ở bảng routing của mỗi node.

Narada dùng mesh để lan truyền thông tin membership. Mỗi member định kỳ trao đổi với các neighbour
thông tin mà nó biết về danh sách các member của nhóm multicast (dùng thông điệp refresh). Và đây
Dynamic Network Condition Adapting Multi-Source Multicast Protocol

10


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

cũng là cách Narada dùng để detect xem một member trong mesh có alive hay khơng. Nếu một node Y
khơng nhận thơng điệp refresh từ neighbour X của nó sau một khoảng T thì X sẽ đưa Y vào hàng một hàng
đợi Q của nó, và sau đó nó sẽ chạy một giải thuật để detect có hay khơng Y thực sự chết, nếu Y khơng chết
thì tạo một kết nối mới đến Y thay cho kết nối cũ bị đứt. Và đây cũng là cách mà Narada dùng để repair
mesh. Hình vẽ bên dưới sẽ trình bày chi tiết giải thuật repair mesh này.
Narada cũng có cơ chế tinh chế mesh nhằm đáp ứng tình trạng thay đổi động của network và đưa cấu trúc
mesh từng bước hội tụ về trạng thái tối ưu. Narada thực hiện việc tinh chế mesh bằng cách thêm vào mesh
các link mới có tác dụng giảm latency của mesh và loại bỏ khỏi mesh các link ít được sử trong việc truyền
dữ liệu.
Mỗi node i định kỳ lấy ngẫu nhiên một node j nào đó, và đánh giá xem nếu thêm một link mới từ i đến j
thì tổng phần trăm độ lợi latency giữa i và phần còn lại của mesh đạt được giảm đi bao nhiêu phần trăm.
Nếu con số này lớn hơn một ngưỡng cho trước thì link này sẽ được thêm vào mesh. Dưới đây sẽ trình bày
cho tiết hàm đánh giá độ lợi latency
EvaluateUtility(j)
{
/* i : current member */
utility = 0
for each member m (m not i) begin
CL = current latency between i and m along mesh
NL = new latency between i and m along mesh if edge i - j
were added
if (NL < CL)
utility + = (CL-NL)/CL
end
return utility

}

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

11


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

- i: current member.
- Let Q be a queue of members for which i has stopped receiving sequence number updates for at least Tm
time.
- Let T be maximum time an entry may remain in Q.
- Member runs this periodically and probabilistically deletes a member from the head of the queue. The
deleted member is probed and it is either determined to be dead, or a link is added to it. The scheduling

[ Q is empty ]

[ Head(Q) is present in Q for >= T time ]

[ Q is empty ]

j:=
Dequeue(Q)

[ j is dead ]

add a link to j
prob = Length(Q)/ GroupSize

[ this run matches prob ]

k:=
Dequeue(Q)

[ k is dead ]

add a link to k

Giải thuật repair mesh
Cũng vậy, mỗi node i định kỳ duyệt các neighbour u của nó và đánh giá mức độ hữu dụng của link giữa i
và u cho mục đích truyền dữ liệu. Sau đó node i sẽ chọn một neighbour j có giá trị hữu dụng thấp nhất.
Nếu giá trị hữu dụng của j nhỏ hơn một ngưỡng cho trước thì link giữa i và j sẽ bị loại bỏ. Dưới đây là
trình bày chi tiết hàm đánh giá mức độ hữu dụng của link.
EvaluateConsensusCost(j)
{
/* i : current member */
Costij = number of members for which i uses j as next hop for forwarding packets.
Costji = number of members for which j uses i as next hop for forwarding packets.
return max(Costij , Costji)

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

12


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

}

Routing Entry
target : addre ss
next hop : address
cost

0..*

routing t able

Member Info
address
last sequence number
local time
is dead

<< contains

0..*

contains >>

+neighbour

<<host>>
Member
refresh()
EvaluateUtility()
EvaluateConsensusCost()

group

membership

has >>

1..*

1..*

<<host>>
Member
refresh()
EvaluateUtility()
EvaluateConsensusCost()

queue of members that it has stopped receiving
sequence number updates from for at least Tm
time.

1
Queue

0..*

QueueEntry
address
local time

Mơ hình tổ chức mesh của Narada

Khi một host X muốn join vào nhóm multicast, X đầu tiên contact với một host được biết trước

(Rendezvous Point) cho danh sách các member của nhóm. Rồi X lấy ngẫu nhiên vài member từ danh sách
đó và gửi request yêu cầu trở thành neigbour đến chúng. Sau khi join thành công, X bắt trao đổi thông
điệp refresh với các neighbour của nó.
Khi một member muốn rời nhóm multicast, nó gửi thơng điệp leave đến tất cả các neighbour của nó, và
sau đó sự kiện này sẽ lan truyền trên mesh đến tất cả các member khác.
Về vấn multicast dữ liệu trên mesh, khi một node X nhận được một gói dữ liệu từ một node Z , X duyệt
bảng routing của các neighbour của nó và forward gói dữ liệu này đến các neighbour Y sử dụng X như là
next hop trong đường dẫn ngắn nhất từ chúng (Y) đến node phát của gói dữ liệu này (source node).
Tóm lại, Narada là một protocol rất phù hợp cho mục tiêu của chúng ta về ứng dụng video conference. Và
Narada có tính kháng lỗi rất tốt. Khi một node bị chết đột ngột, thì mesh vẫn có nhiều khả năng khơng bị
phân hoạch. Tuy nhiên protocol này có một số điểm chưa tối ưu như sau:
Hiện thời protocol chỉ sử dụng latency như là thước đo để cost của một link. Nhưng thực tế trong ứng
dụng video conference thì yếu tố băng thơng của link đóng góp một vai trị rất quan trọng bên cạnh
latency trong việc định cost của link khi thêm link mới hoặc routing các gói dữ liệu.
Cơ chế xây dựng mesh khởi đầu và tinh chế mesh chưa đạt được sự tối ưu cao.
Khi xây dựng một cây multicast cho mỗi node phát, Narada không để ý đến cost phát sinh trên một link
khi link đó đã được sử dụng cho một cây multicast khác.

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

13


Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

Các link thuộc về cùng một node có thể share cùng một đường truyền vật lý, như vậy băng thông của các
link đó phụ thuộc lẫn nhau.
1.3 PRISM
PRISM [3] là một kiến trúc hướng đến các ứng dụng streaming dữ liệu với chất lượng cao trên nền IP
như xem truyền hình trực tuyến, video on demand. Do tập trung vào loại ứng dụng này, nên PRISM cần

một cơ sơ hạ tầng network rất mạnh với các server và đường truyền tốc độ cao giữa các server. Có hai loại
server: 1) Live Source: đóng vai trị như là một nguồn phát dữ liệu, một streaming server; 2) Portal: đóng
vai trị như là một edge server, cache và phân phối dữ liệu đến các client. Các ứng dụng trên máy client
phải kết nối đến một portal server này mới có thể hoạt động được.

PRISM Data Plane
Tóm lại với kiến trúc này, hồn tồn khơng thể áp dụng cho ứng dụng video conference của chúng ta.
1.4 Yoid
Yoid [4] là một kiến trúc multicast mục đích chung, hướng tới hỗ trợ nhiều loại ứng dụng khác nhau.
Yoid không đứng tách rời IP multicast, mà tận dụng nó bất cứ nơi nào có thể. Ở những nơi mà IP
multicast hoạt động được thì Yoid thiết lập một nhóm IP multi cast ở đó và xem nhóm này như là một
phần tử đơn trong hoạt động quản lý member. Yoid hỗ trợ cả hai kiến trúc host-based (tất cả các member
trong nhóm multicast đều là endhost) và servered-based (vài member trong nhóm multicast là server).
Yoid hỗ trợ multicast across space và across time (như ứng dụng email, khơng ràng buộc thời điểm nhận),
trong đó IP multicast chỉ hỗ trợ across space.
Với mỗi nhóm multicast Yoid sử dụng hai cấu trúc tree và mesh để truyền dữ liệu và quản lý các member
tương ứng. Mesh có thể được sử dụng để truyền dữ liệu trong những hợp đặc biệt như khi cấu trúc tree bị
phân hoạch do một member trong tree bị chết đột ngột.
Mỗi nhóm multicast có một hay nhiều rendezvous host, host này đứng bên ngồi cấu trúc tree và mesh
của nhóm. Các host này đóng vai trị là điểm nhập, nơi mà các host muốn gia nhập nhóm multicast phải
contact đầu tiên. Và địa chỉ của các rendezvous host này được biết trước bởi các host muốn gia nhập
nhóm. Các rendezvous host chứa danh sách của vài hoặc tất các member trong nhóm multicast.
Cấu trúc tree là một cây n-phân, trong đó n là giá trị được chọn trước. Các node trung gian gọi là transit
member (node nhận và chuyển dữ liệu đến các neighbour khác hoặc là node phát dữ liệu), các node lá gọi

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

14

Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

là leaf member (node chỉ nhận dữ liệu hoặc là một node phát dữ liệu). Trong trường hợp có nhóm IP
multicast (cluster) thì một thành viên trong nhóm được bầu làm head đóng vai trị đại diện cho cả nhóm.
Các thành viên cịn lại của nhóm được gọi là feet. Các feet gửi và nhận dữ liệu đều thông qua head của
nhóm. Hình vẽ dưới đây sẽ minh họa một cấu trúc cây của Yoid. Đường link giữa hai node cha - con có
một mũi tên hướng từ node con đến node cha chỉ để thể hiện quan hệ cha - con.

Yoid Tree Và Các Thuật Ngữ

Các member cố gắng tìm các neighbour (node cha và các node anh em) càng gần chúng càng tốt và dùng
latency làm thước đo mức độ gần nhau giữa các member. Các member có thể giới hạn bản thân chúng chỉ
làm node lá thôi. Một member có thể là một endhost hoặc yoid server. Thông thường yoid server là một
transit member và được cài đặt trong cơ sở hạ tầng mạng với các mục đích tường minh.
Trong cấu trúc mesh, mỗi node X chỉ duy trì một danh sách của các mesh neighbour của nó và mỗi mesh
neighbour này khơng là một tree neighbour của X trong cấu trúc tree nhằm mục đích tránh sự phân hoạch
đồng thời ở hai cấu trúc khi có node bị chết đột ngột. Mỗi mesh neighbour của X là một node Y đó khơng
có mesh link nào nối trực tiếp từ Y đến X. Mỗi node có 3 hoặc 4 mesh neighbour. Các mesh neighbour của
mỗi node được chọn một cách ngẫu nhiên theo cơ chế yoid mesh anycast (một thông điệp được truyền
trong mesh một cách ngẫu nhiên và ngẫu nhiên dừng lại ở một node).
Khi một host muốn join vào nhóm multicast, nó đầu tiên kiểm tra xem có thể join vào một nhóm IP
multicast cục bộ (cluster), động tác này có thể khơng cần contact với rendezvous server. Nếu khơng có
cluster nào để join vào, nó sẽ bắt đầu q trình tìm một parent cịn đủ khả năng để nhận nó làm con và
parent này là node gần nó nhất mà nó biết được.
Khi một member muốn rời nhóm multicast, nó đầu tiên gửi một thơng điệp đến rendezvous server để
thơng báo việc rời nhóm và cảnh báo các children của nó về sự kiện này.

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

15

Xây Dựng Giải Thuật Phân Bố Dữ Liệu Trên Mạng Internet

Yoid cũng thực hiện việc tinh chế cấu trúc tree theo định kỳ. Mỗi member I định kỳ chọn ra một member
X trong danh sách các member tiềm năng sao cho X gần nó nhất. Nếu X gần I hơn parent J của I thì I sẽ
rời J mang theo các con cháu đến node X và nhận X làm parent mới.
Các member trong danh sách các member tiềm năng của mỗi node I không được là con cháu của I . Mỗi
member I có được danh sách các member tiềm năng (stand-by member hay là các member cịn có đủ chỗ
để nhận member khác làm con) bằng cách : 1) từ rendezvous server khi join nhóm multicast; 2) từ thông
tin trong các thông điệp điều khiển khác nhau như root path của các member khác, intent to join path; 3)
được dùng khi danh sách khơng có đủ số stand-by member cần thiết (có thể một số member trong danh
sach đã khơng cịn là stand-by member). Member I duyệt con cháu của các member trong danh sách này
để tìm các stand-by member cần thiết; 4) dùng yoid tree-any cast. Gửi thông điệp member discovery đến
node cha. Khi danh sách đầy thì các entry cũ nhất sẽ bi loại bỏ.
Khi một member X tìm được một parent gần nó nhất, nó bắt đầu gia nhập với parent mới (đem theo cả con
cháu) và gửi thông điệp root path (tập hợp các member trong path từ X đến root) đến các con cháu của nó.
Nếu một member nhận root path từ cha của nó và root path này cũng chứa chính bản thân nó, thì member
bắt đầu q trình chọn một parent khác vì đã có một chu trình (loop) trong cấu trúc tree chứa member và
node gửi thông điệp root path này. Yoid có cơ chế phát hiện ra loop có thể xảy trước khi join với một
parent. Tuy nhiên, khi loop vẫn có thể xảy ra khi có những thay đổi đồng thời về parent.

Loop được hình thành bởi hai thay đổi đồng thời

Dynamic Network Condition Adapting Multi-Source Multicast Protocol

16