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

GUYỄ HỮU TƯỜ G VI H

XÂY DỰ G GIẢI THUẬT TRUYỀ DỮ LIỆU
HÓM TRÊ MẠ G I TER ET
Chuyên ngành: Khoa học Máy tính

LUẬ VĂ THẠC SĨ

TP. HỒ CHÍ MI H, tháng 07 năm 2009


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 : Tiến sĩ Thoại Nam .............................................

Cán bộ chấm nhận xét 1 : Tiến sĩ Lê Ngọc Minh ..............................................

Cán bộ chấm nhận xét 2 : Tiến sĩ Võ Văn Khang .............................................

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 . 25. . tháng . 8. . năm .2009 .


ðẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ 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 . 1. . tháng . 3. . năm .2009.

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: Nguyễn Hữu Tường Vinh . . . . . . … Phái: Nam……………..
Ngày, tháng, năm sinh: 10/06/1980 Nơi sinh: Hồ Chí Minh
Chuyên ngành: Khoa học máy tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSHV: 00706158. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1- TÊN ðỀ TÀI:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
XÂY DỰNG GIẢI THUẬT TRUYỀN DỮ LIỆU NHÓM TRÊN MẠNG INTERNET.
2- NHIỆM VỤ LUẬN VĂN: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Xây dựng giải thuật N-Tree mở rộng khắc phục các nhược ñiểm của giải thuật N-Tree hiện
tại nhằm ñáp ứng nhu cầu thực tế.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..................................................... .................
............................................... .......................
......................................................................
..................................................... .................
............................................... .......................
......................................................................
..................................................... .................
............................................... .......................
......................................................................
3- NGÀY GIAO NHIỆM VỤ: . .1/2/2009 . . . . . . . . . . . . . . . . . . .
4- NGÀY HOÀN THÀNH NHIỆM VỤ:. . 3/8/2009. . . . . . . . . . . . . . . . . . .
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN (Ghi ñầy ñủ học hàm, học vị): 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 CHỦ NHIỆM BỘ MÔN
KHOA QL CHUYÊN NGÀNH
(Họ tên và chữ ký)
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)
(Họ tên và chữ ký)

TS. Thoại Nam

TS. ðinh ðức Anh Vũ

TS. Thoại Nam


Trang i

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 03 tháng 07 năm 2009

Nguyễn Hữu Tường Vinh

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)



Trang ii

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.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang iii

TÓM TẮT LUẬN VĂN
Với sự phát triển mạnh mẽ của internet ngày nay, cách thức làm việc đã có
nhiều thay ñổi. Người lao ñộng trong một số trường hợp đã khơng cần phải có mặt
tại cơng ty để làm việc mà chỉ cần làm việc tại nhà nhưng vẫn ñảm bảo ñược tiến ñộ
công việc và năng suất làm việc. Thành cơng này có được dựa trên đóng góp không
nhỏ của sự phát triển hội thoại video và nền tảng môi trường cộng tác mà internet
mang lại.
ðể cung cấp cơ sở hạ tầng giúp cho người lao ñộng dễ dàng làm việc, ñề tài
luận văn này ñã ñưa ra cách thức xây dựng cây truyền nhận hỗ trợ việc truyền dữ
liệu nhóm qua mạng internet, đây là tiền đề thiết yếu cho hội thoại video và làm
việc cộng tác. Với hạn chế về các liên kết trong nhóm của giải thuật N-Tree trước
đó, dẫn đến việc đo đạc và áp dụng vào thực tế gặp nhiều khó khăn. Trong luận văn

này, tác giả ñã khắc phục ñược các hạn chế về liên kết ñồng thời ñưa vào các kĩ
thuật như lưu trữ các bước ñã duyệt qua, các kinh nghiệm tìm kiếm mới để đảm bảo
dù số liên kết lớn nhưng giải thuật vẫn tìm ra kết quả trong thời gian giới hạn là
dưới 1 phút.
Bên cạnh đó, giải thuật cịn được song song hóa trên hệ thống supernode2
nhằm tăng tốc độ tìm kiếm. Trong đó vừa kết hợp giữa việc phân chia tập tìm kiếm
vừa sử dụng cùng lúc nhiều kinh nghiệm giúp việc tìm kiếm trong khơng gian lớn
trở nên nhanh chóng. Với các kết quả đạt ñược, hy vọng giải thuật N-Tree mở rộng
sẽ cung cấp một tiền ñề tốt cho các ứng dụng hội thoại video hay làm việc cộng tác
dựa trên mạng internet, giúp các ứng dụng này ngày càng phát triển mạnh đóng góp
có ích cho cơng việc của người sử dụng.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang iv

ABSTRACT
With the strong development of the internet today, how much working style
has changed. Workers in some cases did not need to be present at the company to do
that just working at home, but still ensure the progress of work and productive
employment. This success is based on contributions is the development of video
conference and collaboration platform environment that provides by internet.

To provide infrastructure to help for employees to easily work, the subject of
this thesis has given way to build plant transfers data support the group through the
Internet, this is the essential precondition for video conversation and collaboration.
With restrictions on the links in the group of N-Tree algorithm earlier, leading to the
measurement and application in practice were difficult. In this thesis, the author has

overcome the limitations associated simultaneously put into storage techniques such
as browsing through the steps, the new heuristic search experience to ensure that
despite the large number of associated cases still find the results in limited time is
less than 1 minute.

In addition, parallel algorithms is also on the supernode2 system to speed up
the search. Which has a combination of split searching space and use the search
heuristic experience concurrently at assisting in the search space quickly becomes
huge. With the results achieved, hopefully extension N-Tree algorithm will provide
a good premise for video applications conversation or collaboration on the internet,
allowing these applications growing strong useful contribution to the work of the
user.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang v

MỤC LỤC
LỜI CAM ðOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
TÓM TẮT LUẬN VĂN ........................................................................................... iii
ABSTRACT .............................................................................................................. iv
MỤC LỤC...................................................................................................................v
DANH MỤC HÌNH .................................................................................................. ix
DANH MỤC BẢNG...................................................................................................x
CHƯƠNG 1:
1


Tổng quan về multicast ...................................................................................3
1.1

Khái niệm..................................................................................................3

1.2

Vịng đời của một nhóm sử dụng multicast..............................................6

1.2.1

Tạo nhóm...........................................................................................7

1.2.2

Xây dựng cây dựa trên các ràng buộc ...............................................8

1.2.3

Truyền nhận thông tin .......................................................................8

1.2.4

Phân rã hay xóa nhóm .......................................................................9

1.3

2

GIỚI THIỆU ðỀ TÀI .......................................................................1


Quản lý chất lượng dịch vụ(QoS) trong nhóm sử dụng multicast............9

1.3.1

Giao thức dựa trên nguồn phát ..........................................................9

1.3.2

Giao thức dựa trên nhân trung tâm..................................................10

Các vấn ñề thách thức của multicast .............................................................10
2.1

Quản lý nhóm động ................................................................................11

2.1.1

Tái định tuyến trong cây multicast..................................................11

2.1.2

Xây dựng lại cây multicast..............................................................12

2.1.3

Thay thế các nút ñại diện trong giao thức nhân trung tâm..............12

2.1.4


Khắc phục lỗi ..................................................................................13

2.2

Các vấn ñề giải quyết tắc nghẽn trong ứng dụng dùng multicast cho hội

thoại video .........................................................................................................13
2.2.1

Hệ thống multicast tin cậy và hệ thống multicast thời gian thực....13

2.2.2

Dựa trên khung ñịnh mức (window-based) hay tỷ lệ (rate-based)..13

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang vi

2.2.3

Vị trí của đơn vị quản lý tắc nghẽn .................................................14

2.2.4

Cơ chế phản hồi...............................................................................15

2.2.5


Multicast ở mức ứng dụng (end-to-end) hay ở mức hỗ trợ phần

cứng (router supported).................................................................................15
3

Mục tiêu và giới hạn của đề tài .....................................................................15

4

Tóm lược những kết quả đạt ñược ................................................................16

5

Cấu trúc luận văn ..........................................................................................18

CHƯƠNG 2:
1

2

Một số giao thức ñề nghị cho ứng dụng multicast ........................................19
1.1

Xcast .......................................................................................................19

1.2

ALMI ......................................................................................................20


1.3

NARADA ...............................................................................................22

1.4

NICE protocol.........................................................................................23

1.5

N-Tree.....................................................................................................24

Các phương pháp truyền và nén dữ liệu video trong ứng dụng multicast ....24
2.1

MCU .......................................................................................................27

CHƯƠNG 3:
1

LÝ THUYẾT NỀN TẢNG .............................................................29

Khảo sát chi tiết về giải thuật n-Tree ............................................................29
1.1

ðịnh nghĩa vấn ñề...................................................................................29

1.2

Thiết kế giải thuật ...................................................................................30


1.2.1

Cơ sở ...............................................................................................30

1.2.2

Thiết kế............................................................................................31

1.3

Vấn ñề hội tụ nhanh (FRC).....................................................................34

1.3.1

Trường hợp vi phạm về ñộ trễ.........................................................34

1.3.2

Trường hợp liên kết bị đứt ..............................................................35

1.3.3

Trường hợp nút bị chết....................................................................35

1.4
2

CÁC CƠNG TRÌNH NGHIÊN CỨU LIÊN QUAN ......................19


Nhận xét..................................................................................................35

Kỹ thuật tìm kiếm trong khơng gian tìm kiếm lớn .......................................36
2.1

ðường đi ngắn nhất của các cặp ñỉnh trong ñồ thị .................................39

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang vii

2.2

Mơ tả về bài tốn ....................................................................................39

2.3

Giới thiệu các giải thuật..........................................................................40

2.3.1

Giải thuật nhân ma trận ...................................................................40

2.3.2

Giải thuật Floy-Warshall.................................................................42

2.3.3


Giải thuật Johnson...........................................................................43

2.4

3

Áp dụng kinh nghiệm trong việc chọn lựa các cạnh ..............................45

2.4.1

Các cạnh thuộc các nút có băng thơng rộng....................................45

2.4.2

Các cạnh có ñộ trễ nhỏ ....................................................................46

2.4.3

Phương pháp phối hợp ....................................................................46

2.5

Lưu nhớ các trường hợp đã duyệt qua....................................................47

2.6

Song song hóa một phần giải thuật.........................................................49

2.6.1


Hạ cấp của cây tìm kiếm dựa trên việc phân tán.............................49

2.6.2

Phối hợp các phương pháp tìm kiếm dựa trên việc phân tán ..........49

Phương pháp xây dựng cây truyền nhận .......................................................50
3.1

Giới thiệu ................................................................................................50

3.2

Thiết kế ...................................................................................................51

3.2.1

Cơ sở ...............................................................................................51

3.2.2

Giải thuật .........................................................................................52

3.3

Các thách thức ........................................................................................54

3.3.1


Vấn ñề về FRC ................................................................................54

3.3.2

Vấn ñề về mở rộng số lượng thành viên trong nhóm......................55

CHƯƠNG 4:

THỰC NGHIỆM.............................................................................56

1

Các tiêu chuẩn đánh giá ................................................................................56

2

Các kết quả thực nghiệm...............................................................................56

3

2.1

ðối với chương trình chạy trên máy để bàn ...........................................56

2.2

ðối với chương trình chạy trên supernode 2 ..........................................59

Kết luận .........................................................................................................62


CHƯƠNG 5:
1

KẾT LUẬN .....................................................................................65

Tổng kết ........................................................................................................65

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang viii

2

Những đóng góp của đề tài ...........................................................................65

3

Hướng phát triển ...........................................................................................66

CHƯƠNG 6:

TÀI LIỆU THAM KHẢO...............................................................67

LÝ LỊCH TRÍCH NGANG......................................................................................... i

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)



Trang ix

DANH MỤC HÌNH
Hình 1.1.......................................................................................................................4
Hình 1.2.......................................................................................................................5
Hình 1.3.......................................................................................................................7
Hình 2.1.....................................................................................................................19
Hình 2.2.....................................................................................................................21
Hình 2.3.....................................................................................................................21
Hình 2.4.....................................................................................................................22
Hình 2.5.....................................................................................................................22
Hình 2.6.....................................................................................................................23
Hình 2.7.....................................................................................................................23
Hình 2.8.....................................................................................................................23
Hình 2.9.....................................................................................................................24
Hình 2.10...................................................................................................................26
Hình 2.11...................................................................................................................26
Hình 2.12...................................................................................................................27
Hình 2.13...................................................................................................................28
Hình 3.1.....................................................................................................................36
Hình 3.2.....................................................................................................................37
Hình 3.3.....................................................................................................................47
Hình 3.4.....................................................................................................................48

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang x


DANH MỤC BẢNG
Bảng 4.1 ....................................................................................................................57
Bảng 4.2 ....................................................................................................................57
Bảng 4.3 ....................................................................................................................58
Bảng 4.4 ....................................................................................................................59
Bảng 4.5 ....................................................................................................................60
Bảng 4.6 ....................................................................................................................60
Bảng 4.7 ....................................................................................................................61
Bảng 4.8 ....................................................................................................................62

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 1

CHƯƠNG 1: GIỚI THIỆU ðỀ TÀI
Ngày nay, với việc phát triển khơng ngừng của Internet, các ứng dụng đa
phương tiện cho phép tương tác ña người dùng trở nên phổ biến hơn. Một trong các
ứng dụng ñang phát triển khơng ngừng là ứng dụng làm việc theo nhóm trực tuyến,
hội thoại video ña người dùng hay ứng dụng chơi game tương tác nhiều người chơi
cùng. Trong lĩnh vực hội thoại video trực tuyến, các sản phẩm chuyên biệt từ phần
cứng ñến phần mềm ñã ñược tiếp thị và bày bán. Tuy nhiên, các sản phẩm hiện có
lại rất đắt tiền đối với người tiêu dùng phổ thơng. ðối với các sản phẩm miễn phí
hiện nay chỉ cho phép hội thoại cùng lúc nhiều người, nhưng nếu thêm video thì chỉ
cho phép thực hiện với một người duy nhất. Từ thực tế đó, nhu cầu phát triển một
sản phẩm hội thoại video ña người dùng, cho phép xem ñược video từ nhiều người
dùng trong một nhóm với giá thành thấp ñang là một nhu cầu cần thiết.
Với sự phát triển mạnh mẽ của Internet tốc ñộ cao, hội thoại video có đóng

góp nhiều ích lợi cho cuộc sống con người. Trong các tổng cơng ty lớn hay các tập
đồn đa quốc gia, việc họp triển khai công việc của các chi nhánh tốn kém nhiều chi
phí cho việc di chuyển của các thành viên dự họp và chi phí tổ chức, nhưng nhờ sự
phát triển của hội thoại và video trực tuyến chi phí cho các cuộc họp sẽ được giảm
đáng kể do người tham gia khơng cần phải di chuyển mà chỉ cần ở tại nơi làm việc
và sử dụng các phương tiện phục vụ cho việc họp từ xa. Bên cạnh đó, ngày nay do
đặc thù của một số cơng việc, người làm việc khơng cần có mặt tại cơng ty nhưng
vẫn có thể làm tốt cơng việc của mình mọi thơng tin chi tiết hay họp hành ñều có
thể thực hiện tại nhà chỉ cần họ trang bị một số thiết bị chuyên dụng. Từ những ứng
dụng trên tác giả thấy được việc xây dựng thành cơng một hệ thống hội thoại và
video trực tuyến sẽ ñem lại nhiều ích lợi cho xã hội.
Tuy nhu cầu và ứng dụng rất lớn nhưng hội thoại video trực tuyến khơng thể
phát triển nhanh chóng do cịn gặp phải nhiều thách thức. Một trong những vấn đề
khó khăn chính là chất lượng dịch vụ và băng thông của ứng dụng, trong một cuộc
ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 2

hội thoại trực tuyến giữa một nhóm năm người, ứng dụng của chúng ta sẽ chiếm
băng thơng để gửi cùng lúc bốn hình ảnh của những người khác đến cho người còn
lại và cũng tương tự cho những người khác. Do đó lượng băng thơng cần sử dụng
khơng nhỏ, để giảm bớt chi phí về lượng băng thơng các nhà nghiên cứu cố gắng
tìm ra con đường ngắn nhất để có thể gửi tín hiệu đi đến các điểm cịn lại hay thực
hiện việc nén dữ liệu video để giải dung lượng truyền hoặc sử dụng cả hai phương
pháp trên.
Trong phương pháp tìm đường ngắn nhất, hiện nay có hai cách tiếp cận chủ
yếu. Cách thứ nhất là dựa trên giao thực IP multicast đã có, điểm hạn chế của
phương pháp này chính là số lượng địa chỉ IP multicast rất hạn chế cộng với giao

thức liên lạc tổng quát nên không phù hợp cho ứng dụng hội thoại. Cách tiếp cận
thứ hai là dựa vào unicast xây dựng một cây truyền dữ liệu sao cho thời gian và
dung lượng đường truyền là ít nhất có thể. Trong những năm gần ñây, phương pháp
này ñược các nhà nghiên cứu tập trung phát triển. ðiểm thách thức lớn nhất của
phương pháp này chính là việc làm sao xây dựng được một cây truyền dẫn tối ưu
trong thời gian sớm nhất có thể được. Do bài tốn xây dựng cây được chứng minh
là bài tốn NP-đầy đủ nên thời gian để ñạt ñược nghiệm tối ưu là khá lớn. Vì vậy,
tìm ra giải thuật cho ra kết quả gần tối ưu trong thời gian giới hạn là bài tốn chính
của phương pháp này. Chúng ta sẽ lần lượt xem xét các cách tiếp cận trên một cách
chi tiết hơn ở những phần sau của báo cáo này.
Bên cạnh phương pháp tìm ñường ngắn nhất, phương pháp nén video cũng là
một hướng tiếp cận giúp giảm đáng kể chi phí về dung lượng ñường truyền. Hiện
nay, các hướng ñang ñược ứng dụng để giải quyết bài tốn chính là nén hình ảnh
tổng thể và nén theo các đối tượng trong hình ảnh. Việc nén hình ảnh này giúp cho
dung lượng truyền giảm nhưng địi hỏi tăng việc xử lý hình ảnh ở nơi phát cũng như
nơi nhận. Do đó phương pháp này chỉ hiệu quả khi thiết bị đầu cuối có năng lực xử
lý tín hiệu mạnh. Với việc phát triển ngày càng mạnh về năng lực tính tốn của các
ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 3

CPU hiện nay, cũng như giá thành ngày càng rẻ của chúng, việc có một thiết bị đầu
cuối tính tốn mạnh khơng cịn lại việc khó khăn.

Cuối cùng, trong báo cáo này ta sẽ tập trung giới thiệu và phân tích các yếu tố
then chốt cũng như các thách thức của hội thoại video trực tuyến và ñưa ra các
hướng phát triển ñề tài luận văn nhằm xây dựng một cách thức truyền dẫn video tốt
nhằm thỏa mãn các ràng buộc về băng thơng và độ trễ của ứng dụng. Bên cạnh đó,

cũng đưa ra cách thức dự đốn các tắc nghẽn để phịng tránh và cuối cùng là xây
dựng cơ chế có khả năng phục hồi ứng dụng khi có một điểm nhận bị lỗi hay một
điểm thốt khơng tham gia vào nhóm truyền nhận.
Như được đề cập trong phần trên, vấn đề bài tốn mà báo cáo này muốn tiếp
cận chính là xây dựng một mơ hình truyền nhận cho vấn ñề hội thoại video trực
tuyến ña người dùng. Mục tiêu là cho phép một nhóm nhỏ người sử dụng có thể hội
thoại video với nhau theo mơ hình multicast n-to-n và đảm bảo các ràng buộc về độ
trễ và băng thơng.

1
1.1

T ng quan v multicast
Khái niệm
Xét trong mạng máy tính chúng ta có các loại truyền nhận dữ liệu là unitcast,

multicast. Với unicast là trường hợp truyền từ một ñiểm này ñến một ñiểm khác,
trong khi ñó multicast là cách thức truyền từ một ñiểm ñến tất cả các điểm khác
trong cùng một nhóm, cịn gọi là broadcast, hay các thức truyền thơng tin từ một
nhóm đến một nhóm khác như hình 1.1.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 4

1-to-n (broadcast)
Unicast


n-to-m
Multicast

Hình 1.1

ðối với các cách thức truyền nhận trên, về phần cứng đã được chuẩn hóa và hỗ
trợ từ khi bắt ñầu xây dựng hệ thống mạng máy tính dựa trên IP. Tuy nhiên do dựa
trên địa chỉ IP nên cách thức hỗ trợ cho vấn ñề multicast rất tổng quát. Trong trường
hợp gửi broadcast, các nhà thiết kế dành riêng một loại ñịa chỉ ñặc biệt, gọi là địa
chỉ broadcast, khi ta muốn gửi thơng tin cho một nhóm thì ta chỉ cần gửi tin đến địa
chỉ ñặc biệt cho nhóm ñó, lập tức phần cứng sẽ tạo các bản sao của thơng tin rồi gửi
đến cho các ñịa chỉ nằm trong cùng một mạng của ñịa chỉ broadcast. Cịn trường
hợp multicast n-to-n thì phần cứng dành ra một số ñịa chỉ mạng riêng dùng cho
multicast, khi một máy tính muốn tham gia nhóm multicast thì sẽ cấu hình IP của
mình giống với IP mulicast của nhóm, việc gửi thơng tin cho nhóm đơn thuần là gửi
thơng tin ñến cho ñịa chỉ IP multicast. Các phương pháp này, có một điểm hạn chế
là số lượng địa chỉ IP dành riêng cho multicast bị giới hạn, khi số lượng ứng dụng
multicast trở nên lớn hơn sẽ dẫn ñến việc thiếu các ñịa chỉ IP này dẫn tới giới hạn số
lượng các ứng dụng trên multicast. Bên cạnh đó yếu tố bảo mật và bảo đảm thơng
tin cũng bị ảnh hưởng khi sử dụng IP multicast do chỉ cần cấu hình địa chỉ IP trùng
với IP multicast, một người nào đó có thể có được thơng tin được gửi trong nhóm
sử dụng multicast dù thơng tin đó đã được mã hóa hay biến đổi.
Do những hỗ trợ hạn chế của phần cứng việc xây dựng một ứng dụng tương
tác nhóm dùng multicast n-to-m, dựa trên cách truyền nhận unicast là cách thức
ñang ñược các nhà phát triển phần mềm tập trung nghiên cứu trong thời gian gần
ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 5


đây. Trong hình 1.2 ta sẽ thấy có thể thay thế cách thức gửi thơng tin theo nhóm dựa
trên sự hỗ trợ của phần cứng bằng các sử dụng gởi thơng tin dựa trên cây multicast
dùng unicast.

A
C

R1

R2

(a)

D

B

A
C

R1

R2

(b)

D

B


A
C

R1

(c)

R2

D

B

Hình 1.2

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 6

Trong hình 1.2(a) nút A gửi thơng tin đến cho các nút B, C, D thông qua hỗ trợ
multicast của 2 ñịnh tuyến R1 và R2, nút A chỉ gửi một thơng tin đi một lần đến
định tuyến R1, ñịnh tuyến R1 và R2 có chức năng multicast sẽ tự ñộng tạo ra các
bản sao ñể gửi cho các nút B, C, D có cấu hình sử dụng chức năng multicast. Chúng
ta cũng có thể thực hiện được cơng việc gửi thơng tin từ nút A đến cho các nút cịn
lại nhưng khơng sử dụng chức năng multicast được cung cấp của phần cứng bằng
cách xây dựng các cây gửi thơng tin như trong hình 1.2(b) hay 1.2(c), trong hình
1.2(b) thơng tin cần gửi sẽ được nhân bản sau ñó lần lượt ñược gửi ñến cho các nút

B, C và D, trong khi đó ở hình 1.2(c) thơng tin ñược gửi ñến cho B và C, rồi sau ñó
từ C thơng tin được nhân bản gửi đến cho D. Các cây gửi nhận này thường ñược gọi
là cây gửi nhận multicast và nhóm các nút A, B, C, D ñược gọi là nhóm sử dụng
multicast. Việc thành lập nhóm hay việc xóa bỏ một nhóm multicast, thường được
gọi là vịng đời của một nhóm multicast, ln chịu ảnh hưởng của các yếu tố sau: sự
thay ñổi về số lượng thành viên trong nhóm, sự thay đổi của mạng kết nối các thành
viên và cuối cùng là sự thay ñổi của băng thơng truyền dẫn giữa các thành viên
trong nhóm.

1.2

Vịng đời của một nhóm sử dụng multicast
Vịng đời của một nhóm sử dụng multicast thường trải qua các giai đoạn sau:

• Giai đoạn tạo lập nhóm
• Xây dựng cây multicast với các ràng buộc về tài nguyên, như ñộ trễ và băng
thơng
• Truyền nhận thơng tin trong nhóm
• Phân rã hay xóa nhóm
Các vấn đề trong vịng đời của một nhóm sử dụng multicast được miêu tả
trong hình 1.3

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 7

Tạo nhóm


ðịnh danh
nhóm

u cầu lập
nhóm multicast

Cây
multicast

ðịnh
tuyến
multicast

Thay đổi
nhân
trung tâm

Ràng
buộc tài
ngun

Chất lượng nhân
trung tâm suy giảm

Thiết lập
nhóm

Quản
lý hoạt
động


ða nguồn
gửi

Nhân trung tâm
mới
Tái cấu
trúc cây
multicast

Chất lượng cây
suy giảm
Cây multicast
mới

Vấn ñề
ñường truyền
ðiều chỉnh

Quản
lý lưu
lượng

Tham gia/ rời nhóm

Tái cấu
hình
Xử lý
lỗi


Truyền
nhận
thơng tin

Thứ tự
ưu tiên

Nút hay
đường
truyền
lỗi

Hết
thời
gian
hoạt
động

Ghép/Cắt
nhánh

Quản lý
ràng buộc
động

Phân rã/
xóa
nhóm

Hình 1.3


1.2.1

Tạo nhóm

Bước đầu tiên trong q trình khởi tạo nhóm là việc chọn ra một định danh
duy nhất cho nhóm, dựa trên định danh này để phân biệt các nhóm khác nhằm đảm
bảo thơng tin gửi trong nhóm này khơng bị thất lạc sang nhóm khác. ðịnh danh này
thơng thường gắn với địa chỉ IP của một nút trung tâm trong nhóm. ðối với nhóm
cố định và hoạt ñộng thường xuyên thì IP sử dụng là IP tỉnh, cịn đối với các nhóm
động chỉ tồn tại trong một khoảng thời gian thì thường sử dụng IP động được gán
cho nút được chọn là nút trung tâm, cịn gọi là host, trong nhóm sử dụng multicast.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 8

1.2.2

Xây dựng cây dựa trên các ràng buộc

Sau quá trình tạo nhóm, bước kế tiếp là việc xây dựng cây multicast cho truyền
nhận thông tin dựa trên các ràng buộc về tài nguyên. Cây multicast ñược xây dựng
phải ñảm bảo các yếu tố sau:
• Thỏa các ràng buộc về tài ngun (độ trễ, thơng lượng, mất dữ liệu)
• Các nút phát tín hiệu sẽ chỉ truyền đi lượng thơng tin cần thiết và ít nhất có
thể
• Cho phép nhiều nút đồng thời cùng phát tín hiệu

Việc xây dựng cây multicast tối ưu ñã ñược biết ñến trong "vấn ñề của Steiner
trong mạng máy tính" và được cho là bài tốn NP-đầy đủ.

1.2.3

Truyền nhận thơng tin

Q trình truyền nhận thơng tin sẽ được thực hiện khi q trình tạo nhóm và
lập cây multicast hồn tất. Trong q trình truyền nhận thường xảy ra các vấn đề
sau:
• Sự thay đổi của các thành viên của nhóm: do việc thay đổi số lượng thành
viên của nhóm, việc lưu giữ thơng tin về các thành viên, thơng tin này sẽ
giúp ích cho việc quản lý các ràng buộc động, như việc gửi thơng tin cho
thành viên mới hay ngưng việc gửi thông tin cho thành viên có lỗi hay rời
nhóm.
• Sự thay đổi của mạng truyền dẫn: việc có lỗi trên đường truyền hay tại một
nút nào đó trong nhóm, sẽ dẫn đến việc thông tin truyền trên cây multicast bị
ngắt quãng. Trong trường hợp này việc tái cấu hình lại mạng hay thay đổi
hướng truyền thơng tin được u cầu nhằm đảm bảo chất lượng dịch vụ mà
hệ thống cung cấp cho các nút cịn lại.
• Các vấn đề trong việc truyền nhận thông tin: việc thông tin bị thất lạc hay lỗi
trong q trình truyền nhận cần được quản lý để đảm bảo tính chính xác của
các thơng tin được truyền trong mạng, nếu có lỗi xảy ra cần có các biện pháp
can thiệp hợp lý.
ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 9


Sự tranh chấp giữa các nút gửi thông tin: trong việc gửi nhận n-to-m multicast,
việc xảy ra lỗi tràn bộ đệm có thể xảy ra tại nút nhận thơng tin khi việc cấu hình cho
bộ đệm khơng hợp lý. Do đó, trong trường hợp nhận thơng tin cùng lúc từ nhiều
nguồn, buộc các nút nhận phải có sự sắp xếp thứ tự ưu tiên ñể ñảm bảo tránh các
trường hợp lỗi về bộ đệm.

1.2.4

Phân rã hay xóa nhóm

Tại một thời điểm nào đó, cơng việc của nhóm multicast đã hồn tất, việc phân
ra nhóm hay xóa nhóm sẽ diễn ra. Trong q trình này cơng việc giải phóng các tài
ngun chiếm giữ sẽ được thực hiện. Phân rã nhóm sẽ hồn tất sau khi phóng thích
định danh multicast của nhóm.

1.3

Quản lý chất lượng dịch vụ(QoS) trong nhóm sử dụng
multicast
Chất lượng dịch vụ là một thử thách lớn cho các ứng dụng sử dụng multicast,

do sự hạn chế của hỗ trợ phần cứng việc dùng cây multicast ñược ñưa ra khơng
ngồi mục đích xây dựng một phần mềm có chất lượng dịch vụ tốt cho người tiêu
dùng. Chất lượng dịch vụ ở đây được hiểu như việc đảm bảo thơng tin được truyền
đi một cách chính xác, nhanh nhất và khơng bị trì hỗn. Việc đảm bảo chất lượng
này là yếu tố then chốt cho sự thành công của một sản phẩm.
ðể cung cấp một sản phẩm tốt về chất lượng dựa trên multicast, q trình định
tuyến và xây dựng cây multicast dựa trên hai giao thức sau: giao thức dựa trên
nguồn phát (source-based protocol) và giao thức dựa trên nhân trung tâm (centerbased protocol).


1.3.1

Giao thức dựa trên nguồn phát

Trong giao thức này chúng ta sử dụng ñường ñi ngắn nhất trong một cây
(shorted path tree) ñể dùng cho việc gửi nhận từ nút phát ñến nút nhận. Mỗi nhánh
của cây multicast là ñường ñi ngắn nhất từ nút phát đến các nút cịn lại của nhóm.
Do đó, độ trễ trong giao thức này là ñộ trễ nhỏ nhất và các nút nhận sẽ nhận ñược
ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 10

tín hiệu nhanh nhất có thể có. Tuy nhiên ñiểm hạn chế lớn nhất của cách tiếp cận
này chính là chỉ có thể áp dụng trong một mạng lưới nhỏ, nếu áp dụng trong một
mạng lướt lớn các nút và có khoảng cách xa sẽ khơng khả thi do thời gian để tìm
được đường đi ngắn nhất giữa các nút trong mạng sẽ tiêu tốn rất nhiều thời gian.
Cuối cùng, việc gia nhập hay rồi khỏi nhóm của một nút bất kì có thể ảnh hưởng
đến cấu trúc cây multicast và có thể địi hỏi việc xây dựng lại cây.

1.3.2

Giao thức dựa trên nhân trung tâm

Giao thức này còn ñược gọi là giao thức sử dụng cây chia sẻ (shared-tree
protocol). Việc xây dựng cây multicast dựa trên việc xây dựng từng mảng phủ cho
từng nhánh của cây. ðầu tiên sẽ xây dựng các nút đại diện cho một nhóm các nút
trong một nhánh, nút đại diện cịn gọi là nút hạt nhân, cuối cùng là việc liên kết các
nút hạt nhân lại với nhau hình thành nên cây multicast. Việc gửi thơng tin từ một

nút nào đó đến nút khác sẽ được gửi thơng qua các nút đại diện rồi từ đó chuyển đến
nút hay nhóm nút nhận. Với cách thức trên việc gia nhập hay rời khỏi nhóm của
một nút bất kì sẽ chỉ ảnh hưởng đến cấu trúc nhánh của cây multicast và nút hạt
nhân ñại diện cho nút vừa mới tham gia hay rời ñi.
Gần ñây, một vài giao thức kết hợp giữa hai giao thức trên của ñược ñưa ra
thử nghiệm, cho phép các nút trong nhóm có thể chuyển đổi cách thức hoạt động từ
dùng ñường ñi ngắn nhất kết hợp với nút ñại diện để có được chất lượng dịch vụ tốt
nhất.

2

Các v n ñ thách th c c a multicast
Bên cạnh vấn ñề về các giao thức xây dựng cây multicast tại thời ñiểm khởi

tạo, nhằm ñáp ứng tốt nhất các yêu cầu của người sử dụng, các ứng dụng dựa trên
multicast cịn phải đối mặt với các thách thức như quản lý nhóm động, khắc phục
lỗi, và giải quyết tắc nghẽn.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 11

Quản lý nhóm động

2.1

Ngồi các giao thức dùng để ñịnh tuyến và xây dựng cây multicast ñã ñược ñề
cập ở trên, ñể ñảm bảo cho chất lượng dịch vụ chúng ta khơng thể khơng quan tâm

đến việc thay đổi số lượng thành viên trong nhóm multicast. Việc quản lý nhóm
động này gặp phải các vấn đề sau:
• Tái định tuyến trong cây multicast
• Xây dựng lại cây multicast
• Thay thế các nút ñại diện trong giao thức nhân trung tâm
• Khắc phục lỗi

2.1.1

Tái định tuyến trong cây multicast

Trong một cây multicast việc số lượng thành viên trong nhóm thay ñổi sẽ ảnh
hưởng ñến việc gửi thông tin giữa các thành viên. ðể tránh việc việc gửi thông tin
dư thừa hay thành viên mới khơng nhận được thơng tin, khi một thành viên rời
nhóm hay thành viên mới gia nhập vào nhóm thì sẽ gửi một thơng điệp thơng báo
để ứng dụng có thể cắt bớt nhánh của thành viên rời khỏi hay mở rộng nhánh cho
thành viên mới, quá trình này được gọi là tái định tuyến trong cây multicast. Trong
khi q trình cắt bớt nhánh có thể khơng tốn nhiều cơng sức thì việc thêm nhánh
trong cây multicast là một vấn đề khó khăn. ðể đảm bảo yếu tố chất lượng dịch vụ,
khi một thành viên mới muốn gia nhập nhóm ứng dụng cần phải tìm cho được
đường ñi ñến tất cả các thành viên hiện tại của cây sao cho thỏa mãn các ràng buộc
về tài nguyên của hệ thống, như ràng buộc về ñộ trễ và băng thơng để gửi thơng tin,
nếu điều này được đảm bảo thì thành viên mới mới được kết nạp vào nhóm hiện tại.
Vấn đề này được xếp vào nhóm NP-đầy ñủ và các phương pháp giải hiện nay
thường dựa trên kinh nghiệm (heuristic solutions). Ngồi các ràng buộc nêu trên
cịn có một số ràng buộc cho bài tốn tái định tuyến trong cây multicast là:
• Tăng xác suất thành cơng cho việc gia nhập nhóm
• Tối thiểu chi phí cho việc xây dựng nhánh trong việc kết nạp thành viên mới
• Tối thiểu thời gian gia nhập
• Thích nghi và ñáp ứng tốt với mạng nút lớn

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)


Trang 12

Dựa trên việc mở rộng nhánh của cây multicast cho phép thêm thành viên mới
vào, ta có hai cách thức ñể thực hiện. Cách thứ nhất là ñưa ra vị trí mà thành viên
mới sẽ được thêm vào và cách thứ hai là đưa ra nhiều vị trí có khả năng và tuy theo
tiêu chí đánh giá mà thành viên mới sẽ chọn lựa vị trí tốt nhất cho mình.

2.1.2

Xây dựng lại cây multicast

Trong việc thêm hay bớt thành viên trong nhóm multicast, làm sao đảm bảo
khơng làm ứng dụng bị ngưng trệ là một việc làm quan trọng, nhưng trong một số
trường hợp việc tái ñịnh hướng dẫn tới ảnh hưởng chất lượng dịch vụ địi hỏi ứng
dụng phải tái xây dựng cây multicast ñể ñảm bảo chất lượng dịch vụ. Quá trình tái
xây dựng cây multicast sẽ ảnh hưởng đến ứng dụng, do đó việc làm này cần ñược
tiến hành sao cho việc chuyển từ cây cũ sang cây mới phải ít tốn kém nhất và hạn
chế thấp nhất việc gián ñoạn ứng dụng. Nhằm thỏa mãn chất lượng dịch vụ chúng ta
thường dùng cách thức theo dõi chất lượng dịch vụ và sẽ kích hoạt việc tái xây
dựng lại cây multicast khi chất lượng dịch vụ giảm xuống dưới mức qui ñịnh.

2.1.3

Thay thế các nút ñại diện trong giao thức nhân trung tâm

Giống như tái xây dựng cây multicast, trong giao thức dựa trên nhân trung

tâm, việc suy giảm chất lượng dịch vụ khi nhân trung tâm có sự cố hoặc lỗi địi hỏi
chúng ta phải thay thế nút ñại diện này. Việc thay thế nút ñại diện ñặt ra yêu cầu mà
chúng ta cần giải quyết đó là khi nào phải thay thế nút đại diện, do việc thay ñổi này
sẽ làm gián ñoạn dịch vụ mà ứng dụng cung cấp. Bên cạnh đó, đơi khi việc thay thế
nút đại diện vẫn khơng đem lại kết quả tốt bắt buộc ứng dụng phải tái xây dựng lại
cây multicast. Cuối cùng nhằm ñảm bảo chất lượng dịch vụ, chúng ta sẽ phải cân
nhắc việc áp dụng cách thức tái ñịnh tuyến hay thay thế nút ñại diện cũng như tái
xây dựng lại cây multicast sao cho việc gián đoạn dịch vụ là ít nhất và chi phí là nhỏ
nhất.

ðề tài: Xây dựng giải thuật truyền dữ liệu nhóm trên mạng internet
Học viên: Nguyễn Hữu Tường Vinh (00706158)