HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG NGUYỄN THỊ THÙY ANH

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN LẬP LỊCH TỐI
ƯU TRÊN MẠNG NGANG HÀNG (P2P)

Chuyên ngành: HỆ THỐNG THÔNG TIN
Mã số: 60.48.01.04 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2013

Luận văn được hoàn thành tại:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS VŨ VĂN THỎA Phản biện 1: ………………………………………………………

Phản biện 2: ……………………………………………………

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ
tại Học viện công ngện công nghệ Bưu Chính Viễn Thông

vấn đề lựa chọn cơ chế kéo/đẩy dữ liệu hợp lý giữa các nút (peer)
trong mạng. Việc sử dụng thuật toán lập lịch cụ thể trong mạng
ngang hàng có ảnh hưởng rất lớn đến các tham số hiệu năng của hệ
thống mạng như: trễ (Delay), tỷ lệ mất gói (Packet Loss), băng
thông (Bandwidth), … Đã có nhiều tác giả quan tâm nghiên cứu và
đề xuất nhiều thuật toán lập lịch tối ưu. Do đó, học viên chọn đề tài
“Nghiên cứu một số thuật toán lập lịch tối ưu trên mạng ngang
hàng (P2P)” cho luận văn tốt nghiệp thạc sĩ.
Căn cứ mục tiêu và yêu cầu nghiên cứu, đề tài được bố cục
gồm các phần sau:

2

MỞ ĐẦU
CHƯƠNG 1: TỔNG QUAN VỀ MẠNG NGANG HÀNG.
Trong chương này luận văn tiến hành khảo sát những vấn đề
chung về mạng ngang hàng và vấn đề lập lịch trong mạng ngang
hàng.
CHƯƠNG 2: CÁC THUẬT TOÁN LẬP LỊCH TỐI ƯU TRONG
MẠNG NGANG HÀNG.
Chương 2 sẽ trình bày một số thuật toán lập lịch tối ưu trong
mạng ngang hàng cho một số mạng phổ biến hiện nay như sau:
- Mạng hình lưới không cấu trúc kết nối hoàn toàn (Full Mesh - FM).
- Mạng chồng phủ truyền tải dữ liệu DON (Data-driven
Overlay Networks).
- Mạng chồng phủ truyền tải streaming trực tiếp (Live
Streaming System).

nút) gặp phải sự cố.
Đảm bảo tính sẵn sàng cao, chi phí xây dựng thấp.
1.1.3 Ứng dụng của mạng ngang hàng
1.1.3.1 Chia sẻ tài liệu

4

1.1.3.2 Ứng dụng phân tán tính toán
1.1.3.3 Ứng dụng hợp tác
1.1.3.4 Ứng dụng lớp nền
1.2 Phân loại mạng ngang hàng
Mạng ngang hàng có thể phân loại theo tiêu chí mục đích sử
dụng hoặc tiêu chí mức độ phân tán (hay tập trung) và cấu trúc của
mạng.
Theo tiêu chí mục đích sử dụng có thể kể ra một số mạng
ngang hàng như:
- Mạng chia sẻ file (file sharing)
- Mạng điện thoại VoIP (telephony)
- Mạng đa phương tiện media streaming (audio, video)
- Diễn đàn thảo luận (Discussion forums)
Theo tiêu chí mức độ phân tán và cấu trúc của mạng có thể kể
ra một số mạng ngang hàng như:
- Mạng ngang hàng không cấu trúc (unstructured) bao gồm:
+ Mạng ngang hàng tập trung (Cetralized)
+ Mạng ngang hàng thuần túy (Pure)
+ Mạng ngang hàng lai (Hybrid)
- Mạng ngang hàng có cấu trúc (structured)


1.2.1.2 Mạng ngang hàng thuần túy
Trong mạng ngang hang thuần túy các peer giao tiếp trực tiếp
với peer khác trong mạng mà không cần các máy chủ trung tâm
riêng biệt nào. Các peer thiết lập kết nối với nhau ngẫu nhiên.
Trong mạng ngang hàng thuần túy, quá trình tìm kiếm dữ liệu
sử dụng phương pháp phát tràn (Flooding).
Mạng ngang hàng thuần túy có các ưu, nhược điểm sau đây.
Ưu điểm:
- Hệ thống mạng dễ xây dựng;
- Khắc phục hiện tượng nút cổ chai;
- Đảm bảo tính phân tán hoàn toàn: Các node tham gia mạng
và rời khỏi mạng một cách tùy ý mà không ảnh hưởng đến cấu trúc
của mạng.
Nhược điểm:
- Tốn băng thông: Các node có khả năng khác nhau(CPU
power, bandwidth, storage) đều có thể phải chịu tải(load) như nhau.
- Quá trình tìm kiếm dữ liệu phức tạp.
1.2.1.3 Mạng ngang hàng lai
Mạng ngang hàng lai có các ưu điểm sau đây.

7

- Hạn chế việc flooding các query, làm giảm lưu lượng trong
mạng, nhưng vẫn tránh được hiện tượng nút cổ chai (do có nhiều
Super peers).
- Khắc phục được nhược điểm về sự khác nhau về CPU power,

tiếp đến hiệu năng của hệ thống P2P. Một lịch trình phân phối dữ
liệu kém có thể làm cho thời gian tải dữ liệu về lâu hơn rất nhiều.
Trong khi đó, một lịch trình tốt có thể rút ngắn thời gian hoàn thành
và tối ưu việc sử dụng các nguồn tài nguyên mạng.
1.3.2 Mô hình lập lịch đẩy (Push)
1.3.3 Mô hình lập lịch kéo (Pull)
1.3.4 Mô hình lai kết hợp đẩy/ kéo (Push/ Pull)
Trong mô hình kết hợp Push/ Pull, mỗi nút mạng là độc lập và
không đồng bộ với nguồn hoặc với các peer khác.
1.4 Kết chương
Trong chương này luận văn đã khảo sát những vấn đề chung
về mạng ngang hàng và vấn đề lập lịch trong mạng ngang hàng.
Mặc dù vẫn còn những vấn đề về bảo mật, về bản quyền của những
nội dung được trao đổi, nhưng với những ưu thế và lợi ích mà mạng

9

ngang hàng đem lại, mạng ngang hàng cần phải được tiếp tục
nghiên cứu và phát triển.
Trên cơ sở các nội dung nghiên cứu trong chương 1, chương 2
sẽ nghiên cứu một số thuật toán lập lịch tối ưu trong các mạng
ngang hàng phổ biến.
c
chunk. Mỗi peer P
i
nhận
chunk C
j
từ các peer khác và sau đó gửi chúng đi với tốc độ s(P
i
).

11
Nguồn gửi các chunk với tốc độ s(source). Tập các chunk vừa được
P
i
nhận tại thời điểm t được kí hiệu là C(P
i
, t).
2.1.2 Lập lịch peer tối ưu
Cơ sở lựa chọn peer tối ưu đó là: peer đích được lựa chọn phải
có thể ngay lập tức tham gia vào quá trình phân bổ chunk.
Khảo sát lập lịch peer “Earliest Latest” ELp.

Hình 2.1: Thuật toán lập lịch peer Elp

2.1.3 Lập lịch chunk tối ưu
Lập lịch cho chunk có thể có nhiều dang. Ở đây luận văn chỉ
khảo sát hai thuật toán lập lịch RUc (Random Useful Chunk) và Dl
13
2.2.3 Các thuật toán tìm phương án lập lịch tối ưu
2.2.3.1 Thuật toán đơn hình
Trình bày thuật toán đơn hình.
2.2.3.2 Thuật toán tìm luồng với chi phí nhỏ nhất
Trình bày thuật toán tìm luồng với chi phí nhỏ nhất.
2.2.3.3 Thuật toán phân phối Heuristic
Trình bày thuật toán phân phối Heuristic.
2.3 Lập lịch tối ưu cho mạng truyền tải video trực tiếp
2.3.1 Mô hình hóa
Mô tả và mô hình hóa một phiên trực tuyến trên một mạng
chồng phủ như một đồ thị có hướng G = {V, E}, trong đó V là tập
các đỉnh đại diện cho các nút peer và E là tập các cạnh lớp phủ đại
diện cho các liên kết lớp phủ.
2.3.2 Bài toán cực tiểu hóa trễ trung bình end-to-end trong
P2P live streaming
Trình bày bài toán cực tiểu hóa trễ trung bình end-to-end trong
P2P live streaming (Minimizing Average End-to-End Delay in P2P
Live Streaming Systems - MADPS) đưa ra một phương án lập lịch
dòng cực tiểu hóa trễ trung bình end-to-end sao cho tất cả các peer
nhận đều là các peer được phục vụ đầy đủ.

14
2.3.3 Thuật toán xấp xỉ giải bài toán MADPS
Trình bày thuật toán xấp xỉ để giải bài toán MADPS.

trên mạng ngang hàng đã được nghiên cứu trong chương 2. Quá
trình đánh giá các thuật toán lập lịch tối ưu trên mạng ngang hàng
phức tạp. Do đó, trong chương này luận văn sẽ hạn chế tập trung
khảo sát các vấn đề sau:
- Đối với mạng hình lưới không cấu trúc kết nối hoàn toàn
(Full Mesh - FM) sẽ mô phỏng đánh giá hiệu năng trễ (Delay) của
hai thuật toán chunk/peer phối hợp là LUc/ELp và DLc/ELp.
- Đối với mạng chồng phủ truyền tải dữ liệu DON (Data-
driven Overlay Networks) sẽ mô phỏng đánh giá tốc độ trung bình
chia sẻ các block trong mạng.
- Đối với mạng chồng phủ truyền tải streaming trực tiếp (Live
Streaming System) sẽ đánh giá chi tiết thuật toán lập lịch tối ưu
bằng các công cụ toán học chặt chẽ về tốc độ hội tụ và thời gian
thực hiện chương trình.

16
3.1 Mô phỏng đánh giá hiệu năng thuật toán lập lịch tối ưu
trong mạng hình lưới không cấu trúc kết nối hoàn toàn
3.1.1 Đặt bài toán
Xét mạng P2P hình lưới không cấu trúc kết nối hoàn toàn gồm
N nút (peer), không kể nút nguồn. Kí hiệu trễ toàn mạng cho tới khi
tất cả các nút nhận được đầy đủ dữ liệu cần thiết theo yêu cầu trong
trường hợp xấu nhất là F. Theo công thức (2.1) trong mục 2.1, thuật
toán lập lịch là tối ưu nếu F =
2
log
N

với kết quả lý thuyết hơn là DLc/ELp.
3.2 Mô phỏng đánh giá hiệu năng thuật toán lập lịch tối ưu
trong mạng DON
3.2.1 Đặt bài toán
Xét mạng chồng phủ truyền tải dữ liệu DON (Data-driven
Overlay Networks) gồm N nút. Ta định nghĩa tốc độ phân bổ R(i)
các block tại mỗi nút i là tỷ số giữa số lượng các block nút i nhận
được trước hoặc tại thời điểm kết thúc playback và số lượng các
block đã phát.

18
Tốc độ phân bổ trung bình R(tb) là:
R(tb) =
( )
i R
R i


(3.1)
Như vậy giá trị R(tb) như là một hàm của tốc độ dòng trong
mạng DON.
Trong mục này ta sẽ mô phỏng đánh giá R(tb) bằng phương
pháp giải bài toán trong mục 2.2 là phương pháp đơn hình. Giả thiết
là mạng DON không có các nút cổ chai.
3.2.2 Kết quả và đánh giá

Hình 3.2: Kết quả mô phỏng R(tb) cho DON

R(tb) chia sẻ các block trong mạng tương ứng các tốc độ dòng khác
nhau sử dụng phương pháp đơn hình.
- Đối với mạng chồng phủ truyền tải streaming trực tiếp (Live
Streaming System) đã phân tích, đánh giá chi tiết thuật toán lập lịch

20
tối ưu bằng các công cụ toán học chặt chẽ về tốc độ hội tụ và thời
gian thực hiện chương trình.
Các kết quả đánh giá mô phỏng là phù hợp với lý thuyết và mở
ra khả năng ứng dụng các thuật toán lập lịch tối ưu trong các dịch
vụ thực tế.
21

KẾT LUẬN

Luận văn đã đạt được các kết quả chính sau đây:
Luận văn đã khảo sát những vấn đề chung về mạng ngang
hàng, và vấn đề lập lịch cho mạng ngang hàng. Một số thuật toán