1
LỜI MỞ ĐẦU
1. TÍNH CẤP THIẾT CỦA ĐỀ TÀI
Sự phát triển nhanh chóng các ứng dụng truyền video trên
Internet đặt ra những thách thức ngày càng lớn. Để cung cấp môi
trƣờng luồng chất lƣợng cao cho ngƣời dùng cuối, nhiều ứng dụng
video đòi hỏi chất lƣợng dịch vụ mạng (Quality Of Service QoS).Tuy nhiên, do mạng Internet là mạng mặc dù đƣợc xây dựng
với đặc điểm truyền là nỗ lực tối đa (best-effort network) nhƣng chƣa
thể đảm bảo về QoS và không có sự phân biệt giữa các gói tin truyền
trên mạng dẫn đến tỷ lệ đáng kể các gói dữ liệu video bị loại bỏ bởi
các bộ định tuyến mạng khi xảy ra tình trạng thiếu băng thông trên
các đƣờng truyền do bị tắc nghẽn. Ảnh hƣởng của việc mất gói tin
video làm suy giảm chất lƣợng xem ở phía máy nhận có thể thay đổi
từ không đáng kể đến mức không thể chấp nhận đƣợc[15, 19, 55].
Một trong các cơ chế quản lý hàng đợi thƣờng đƣợc sử dụng để tăng
hiệu năng mạng và ngăn cản sự suy giảm chất lƣợng truyền video là
cơ chế quản lý hàng đợi tích cực (AQM - Active Queue Management
[21, 23, 24, 69, 78, 80, 88]).
Đã có nhiều nghiên cứu, bài báo đề xuất giải pháp sử dụng các cơ
chế quản lý hàng đợi tích cực AQM để giải quyết vấn đề tránh tắc
nghẽn, [12, 23, 28, 31, 47, 51, 69, 78, 83, 85, 86, 88, 89],... Tuy
nhiên hầu hết các giải pháp này mới tập trung vào giải quyết vấn đề
xử lý dữ liệu thông thƣờng mà không hề đề cập đến việc ƣu tiên phân
loại luồng dữ liệu cho video. Hoặc chƣa xử lý nó ngay trong bản thân
các giải thuật quản lý hàng đợi cụ thể.
Từ các yêu cầu cấp thiết và thực trạng nhu cầu về các ứng dụng
truyền luồng dữ liệu video trên mạng tác giả đã đi đến lựa chọn
nghiên cứu đề tài luận án: “Nghiên cứu cải tiến phƣơng pháp quản
lý hàng đợi cho truyền video trên mạng IP”
II. MỤC TIÊU NGHIÊN CỨU
Mục tiêu chính của luận án này là đóng góp vào các nghiên cứu
cải tiến phƣơng pháp quản lý hàng đợi cho truyền video dạng chuẩn
Mpeg-4 trên mạng IP.
2
Chúng tôi đã nghiên cứu kỹ các thuật toán quản lý hàng đợi tích
cực RED và đặc biêt là BLUE; đã nghiên cứu kỹ các đặc điểm lỗi
của quá trình truyền video trên mạng IP và ảnh hƣởng của việc mất
gói tin đến hiệu năng và chất lƣợng dịch vụ truyền video. Dựa trên
các kết quả nghiên cứu đó, chúng tôi đã nêu các đề xuất có tính
phƣơng pháp luận để cải thiện hiệu năng và chất lƣợng dịch vụ
truyền video trên các môi trƣờng mạng phức tạp (đa luồng). Các đề
xuất cụ thể của chúng tôi gồm có: 1./ Tích hợp cơ chế ưu tiên gói tin
video trong cơ chế điều khiển hàng đợi tích cực RED; 2/. Xây dựng
các hàm tuyến tính đơn biến và đa biến để cải thiện chất lượng
truyền video; 3/. Đề xuất xây dựng giải thuật cải tiến hàng đợi tích
cực BLUE-VPT cải thiện chất lượng truyền video trên mạng.
2. ĐỐI TƢỢNG VÀ PHẠM VI NGHIÊN CỨU
Đối tƣợng nghiên cứu
Luận án nghiên cứu cải tiến phƣơng pháp quản lý hàng đợi cho
truyền video trên mạng IP. Để thực hiện mục tiêu chính của luận
án, chúng tôi đã nghiên cứu trên các đối tƣợng cụ thể là các cơ
chế quản lý hàng đợi tích cực RED, BLUE. Nghiên cứu cải tiến
các hạn chế của các giải thuật đó trong truyền dữ liệu dạng video
trên mạng IP.
Nghiên cứu đề xuất xây dựng hàm tuyến tính điều chỉnh xác
suất đánh dấu (loại bỏ) gói tin dựa trên các đặc tính của bộ
đệm tại bộ định tuyến và mức độ sử dụng đƣờng truyền của
mạng.
Nghiên cứu phát triển một giải thuật AQM mới là BLUE-VPT
có hiệu năng và chất lƣợng dịch vụ truyền video trên mạng IP
tốt hơn các giải thuật đã có.
Phƣơng pháp đánh giá hiệu năng và chất lƣợng dịch vụ truyền
video trên mạng IP bằng mô hình thực nghiệm mô phỏng trên
bộ công cụ NS-2.
Phạm vi nghiên cứu
+ Tập trung nghiên cứu những hạn chế của các giải thuật quản lý
hàng đợi tích cực AQM là RED và đặc biệt BLUE trong truyền video
dạng Mpeg-4 từ đó phân tích, đề xuất giải pháp cải thiện hiệu năng
3
và chất lƣợng truyền video qua mạng sử dụng các tham số hiệu năng
và thang đo khách quan PSNR(dB) [22, 46, 48, 60, 74, 79, 84] và
thang đo chủ quan MOS [20, 46, 79] để đánh giá.
+ Nghiên cứu đề xuất xây dựng hàm tuyến tính điều chỉnh xác
suất đánh dấu (loại bỏ) gói tin dựa trên kích thƣớc hàng đợi tại bộ
định tuyến và mức độ sử dụng đƣờng truyền, nghiên cứu phân tích
cấu trúc mã hóa liên khung của video từ đó tích hợp cơ chế ƣu tiên
phân loại gói tin trong các giải thuật AQM để cải thiện chất lƣợng
truyền video qua mạng IP.
+ Nghiên cứu đánh giá và cải tiến giải thuật quản lý hàng đợi tích
cực RED, BLUE nâng cao hiệu năng và chất lƣợng dịch vụ truyền
video với các giải thuật cải tiến.
Phƣơng pháp nghiên cứu của luận án
Nghiên cứu lý thuyết:
- Tắc nghẽn và một số giải pháp tránh tắc nghẽn.
- Các cơ chế quản lý hàng đợi (QUEUE), cơ chế quản lý hàng đợi
tích cực AQM (Active Queue Management) nhƣ RED và đặc biệt
là BLUE.
- Các kỹ thuật video MPEG, H.26x.
- Các phƣơng pháp đánh giá hiệu năng và chất lƣợng dịch vụ
mạng.
- Các phƣơng pháp đo lƣờng đánh giá chất lƣợng truyền video
khách quan và chủ quan (PSNR, MOS):
+ Nghiên cứu thực nghiệm: thông qua cài đặt và mô phỏng
truyền video trên mạng IP trên bộ công cụ mô phỏng NS-2
[57](Network Simulator) và khung làm việc EVALVID[20, 46].
+ Phân tích đánh giá: Dựa trên kết quả quan sát trực quan và
các dữ liệu thống kê. Phân tích tổng hợp, kết hợp giữa lý thuyết
và thực nghiệm để chỉ ra các tồn tại hạn chế, nguyên nhân và
giải pháp khắc phục.
+ Tổng hợp, kế thừa: các ƣu điểm và các kết quả nghiên cứu chi
tiết nhỏ để tổng hợp đƣa ra những giải pháp mới có nhiều ƣu
điểm hơn so với các giải pháp đã có trƣớc đó.
4
Hiệu năng và chất lƣợng dịch vụ truyền video khi áp dụng các cơ
chế quản lý hàng đợi tích cực có đề xuất cải tiến của chúng tôi
đƣợc so sánh với các cơ chế RED, BLUE chƣa cải tiến. Chúng tôi
đánh giá hiệu năng mạng và chất lƣợng dịch vụ truyền video
bằng phƣơng pháp mô phỏng, sử dụng công cụ mô phỏng mạng
NS-2, khung làm việc EVALVID và một số tệp tin video
akio.yuv, foremance.yuv từ thƣ viện các tập tin video [8, 20, 46],
tệp tin video bachkhoa.yuv do tác giả quay trực tiếp.
3. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA LUẬN ÁN
Ý nghĩa khoa học của luận án:
(1).Đề tài đã đƣa ra một số thuật toán quản lý hàng đợi áp dụng
cho video để nâng cao chất lƣợng truyền trên mạng IP.
(2). Đề xuất mới giải pháp tính các xác suất loại bỏ gói tin khác
nhau trong hàng đợi tích cực đối với các gói tin video và các gói
tin không phải video.
Ý nghĩa thực tiễn của luận án:
(3). Luận án xây dựng đƣợc mô hình đánh giá các nhân tố ảnh
hƣởng đến hiệu năng và chất lƣợng dịch vụ truyền video trên
mạng máy tính bằng phƣơng pháp mô phỏng trên khung làm
việc EVALVID và bộ công cụ NS-2. Đã thử nghiệm mô phỏng
với luồng video thực.
(4). Đề xuất một số phƣơng pháp điều chỉnh xác suất đánh
dấu/loại bỏ gói tin trong các giải thuật RED, BLUE.
(5). Đề xuất đƣợc một giải thuật cải tiến hàng đợi tích cực áp
dụng cho RED là ViRED. Và một giải thuật cải tiến hàng đợi
BLUE theo kiểu tiền xử lý là BLUE-VPT, chứng minh đƣợc sự
cải thiện chất lƣợng dịch vụ truyền video của các giải thuật cải
tiến này trong các điều kiện mạng đa luồng.
KẾT CẤU CỦA LUẬN ÁN
Nội dung luận án đƣợc kết cấu bao gồm: phần mở đầu, 4
chƣơng chính, kết luận, danh mục tài liệu tham khảo. Trong đó:
4.
5
Lời mở đầu: Nêu lý do, sự cần thiết của đề tài, đối tƣợng và phạm vi
nghiên cứu của đề tài.
Chƣơng 1: TỔNG QUAN VỀ HIỆU NĂNG, CHẤT LƢỢNG DỊCH
VỤ TRUYỀN VIDEO TRÊN MẠNG MÁY TÍNH.
Chƣơng 2: CƠ CHẾ QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRONG
TRUYỀN PHÁT VIDEO TRÊN MẠNG
Chƣơng 3: ĐỀ XUẤT CẢI TIẾN GIẢI THUẬT QUẢN LÝ HÀNG
ĐỢI RED
Chƣơng 4: ĐỀ XUẤT CẢI TIẾN GIẢI THUẬT QUẢN LÝ HÀNG
ĐỢI BLUE.
Kết luận: Tổng kết các kết quả đã thực hiện đƣợc của luận án.
Luận án đã đƣợc bảo vệ tại hội đồng bảo vệ cấp cơ sở tại Viện
Đào tạo Sau Đại học, trƣờng Đại học Bách Khoa Hà Nội; ngày 20
tháng 02 năm 2014.
Một số kết quả nghiên cứu của Luận án đã đƣợc báo cáo tại
Hội thảo Quốc tế, ICUFN 2013 tại Đà Nẵng, Tạp chí IJCSNS
30/10/2013. Tạp chí Tin học và điều khiển học, chuyên san tạp chí
CNTT và truyền thông, Tạp chí khoa học và công nghệ các trƣờng
Đại học.
6
Chƣơng 1. TỔNG QUAN VỀ HIỆU NĂNG, CHẤT LƢỢNG
DỊCH VỤ RUYỀN VIDEO TRÊN MẠNG MÁY TÍNH.
1.1. Khái niệm hiệu năng và chất lƣợng dịch vụ mạng
Chất lƣợng dịch vụ mạng hay QoS mạng, bao hàm gồm cả hiệu
năng và QoS.
1.2. QoS và vấn đề tắc nghẽn
Với nhu cầu truyền thông ngày càng tăng nhất là đối với các ứng
dụng truyền phát video đòi hỏi băng thông cao thì khả năng xảy ra
tắc nghẽn trên mạng lại càng lớn làm ảnh hƣởng đến QoS của các
ứng dụng, đặc biệt trong lĩnh vực truyền phát video [12, 50, 65, 66,
81].
1.3. Video kỹ thuật số
Hiện nay trên thế giới có hai tổ chức chịu trách nhiệm chính trong
việc đƣa ra các chuẩn về nén và giải nén video đó là ITU và ISO.
1.3.1. Chuẩn MPEG
Đƣợc thiết lập từ năm 1988, MPEG[9, 36, 60, 67, 72] là một
nhóm chuyên gia các hình ảnh chuyển động thuộc ISO/IEC, chuẩn
MPEG lần đầu tiên đƣợc ra mắt vào tháng 5 năm 1988 tại Ottawa,
Canada có nhiệm vụ phát triển các tiêu chuẩn mã hóa cho hình ảnh
và âm thanh kỹ thuật số. Cho đến nay, nhóm nghiên cứu này đã phát
triển hơn 350 thành viên từ các hội nghị trên tất cả các lĩnh vực công
nghiệp, các khu nghiên cứu, đến các trƣờng đại học.
1.3.2. Chuẩn H.26L
Video Coding Experts Group (VCEG - ITU-T SG16 Q.6) đã bắt
đầu phát triển các chuẩn H26L từ năm 1998, bao gồm các chuẩn
H.261, H263, H264AVC [9, 72, 73, 74, 75], đến tháng 4/2013 ITU
đã công bố khuyến nghị chuẩn H.265.
1.3.3. Cấu trúc mã hóa video
Với phƣơng pháp mã hoá video hiện đại sẽ mã hóa mỗi khung
thành khung I (khung chính), P (khung hình dự đoán) hoặc B (hai
chiều).
I
B
B
P
B
B
P
B
B
P
B
B
I
B
B
P
B
B
GoP
Hình 1.5 Cấu trúc GoP
P
B
GoP
B
P
B
B
...
7
1.4. Chất lƣợng dịch vụ truyền video trên mạng IP
1.4.1 Kỹ thuật truyền dòng video trên mạng IP
1.4.2 Các tham số QoS
1.4.3 Các đặc tính QoS:
1.4.4 QoS trong mạng IP:
1.4.5 Các độ đo QoS
1.5. Đánh giá chất lƣợng video trên mạng IP
1.5.1. Đánh giá khách quan
Một cách tổng quát đánh giá chất lƣợng video khách quan có thể
phân loại thành ba mô hình đánh giá chất lƣợng video chính [48, 73,
74]: Mô hình tham chiếu đầy đủ (Full-reference-FF), Mô hình không
tham chiếu (Non-reference/Zero-reference-ZF), Mô hình tham chiếu
rút gọn (Reduced-Reference/Partial-Reference - RR) [22, 73]
PSNR(dB): PSNR (Peak signal-to-noise ratio) đƣợc xem nhƣ một
trong các độ đo khách quan nhất để đo chất lƣợng truyền video qua
mạng.
PSNR (n) dB
20 log 10
1
N col N row
V peak
N co l N ro w
2
Y
(
n
,
i
,
j
)
Y
(
n
,
i
,
j
)]
S
D
i 0 j 0
(1.13)
Vpeak = 2k – 1. Trong đó: k là số bit mã hóa một điểm ảnh.
1.5.2. Đánh giá chủ quan
Một trong những phƣơng pháp đánh giá chất lƣợng video cho kết
quả tốt nhất đó là phƣơng pháp đánh giá chủ quan của con ngƣời
(Mean Opinion Score - MOS).
1.5.3. Liên hệ giữa thang đo chủ quan và khách quan.
Mối liên hệ giữa thang đo chủ quan và khách đƣợc trình bày trong
bảng 1.9 chất lƣợng PSNR(dB) của các khung hình đƣợc ánh xạ vào
thang đo kinh nghiệm MOS theo bảng 1.9.
Bảng 1.9 Liên hệ thang đo chủ quan và khách quan
PSNR(dB)
>37
31-37
25-31
20-25
<20
MOS
(Rất tốt)
4(Tốt)
3(Trung bình)
2(Tồi)
Rất tồi
8
Chƣơng 2. CƠ CHẾ QUẢN LÝ HÀNG ĐỢI TÍCH CỰC
TRONG TRUYỀN PHÁT VIDEO TRÊN MẠNG
2.1 Mô hình quản lý hàng đợi
Trong các ứng dụng tƣơng tác và thời gian thực thì thời gian trả
lời trung bình đƣợc xem nhƣ một tiêu chuẩn quan trọng còn trong
các ứng dụng khác thì thông lƣợng lại là điều quan trọng nhất. Việc
mô tả hàng đợi theo lý thuyết toán học rất phức tạp nên ta chỉ mô tả
chúng theo mô hình đơn giản đƣợc sử dụng trong các mạng IP.
2.2 Kiến trúc phân lớp CQS trong Router
2.2.1 Phân lớp
Việc phân loại gói tin cũng là hình thức của cơ chế truyền gói dựa
theo các mức ƣu tiên. Để phân loại lớp các dịch vụ chủ yếu dựa vào
thông tin bên trong phần header của gói. Nếu thiết lập a bit trong
phần header của gói để làm bit phân loại thì ta sẽ phân loại đƣợc 2ª
gói. Các thông tin phân loại đƣợc đặt trong trƣờng TOS của IPv4,
trƣờng TC của IPv6 và trƣờng DS.
0
1
Precedence
3 bit
2
3
4
5
6
7
D
T
R
4 bit TOS
0
0
1 bit
Hình 2.3 Trường TOS của IPv4
2.2.2 Quản lý hàng đợi
2.2.3 Lập lịch
2.2.4 Các tham số cơ bản liên quan tới hàng đợi
2.2.5 Bắt giữ và đánh dấu gói tin
2.2.6 Giảm chiếm giữ hàng đợi
2.3 Cơ chế quản lý hàng đợi bị động
2.4 Cơ chế quản lý hàng đợi tích cực
2.4.1 Khái niệm
Quản lý hàng đợi tích cực (AQM-Active Queue Management) là một
hình thức quản lý hàng đợi của bộ định tuyến tiên tiến/nâng cao cố
gắng để phát hiện và phản ứng/phản hồi/xử lý tắc nghẽn trƣớc khi nó
dẫn đến hậu quả nghiêm trọng khi hàng đợi đầy và bùng phát loại bỏ
gói tin. Khi xử lý nghi ngờ tắc nghẽn, phƣơng pháp AQM loại bỏ
9
sớm các gói tin (hoặc thực hiện đánh dấu ECN) để báo hiệu tắc
nghẽn tới các nút cuối.
2.4.2 Các cơ chế quản lý hàng đợi tích cực.
Theo các số liệu sử dụng để đo tình trạng tắc nghẽn, quản lý hàng
đợi tích cực có thể đƣợc phân thành ba dạng: Quản lý hàng đợi tích
cực dựa vào kích thƣớc hàng đợi, chẳng hạn RED; quản lý hàng đợi
tích cực dựa vào tải nạp BLUE [28, 33, 85, 86]; quản lý hàng đợi tích
cực dựa vào kích thƣớc hàng đợi và tải nạp [15]. Cơ chế quản lý
hàng đợi tích cực để chống tắc nghẽn tại các nút mạng nhƣ RED và
các biến thể của nó ARED[29], ARIO[42],… Trong hình 2.8 trình
bày phân loại các cơ chế quản lý hàng đợi tích cực [23].
Quản lý hàng đợi tích cực
Dựa theo kích thước hàng đợi
Dựa theo tải nạp
Dựa theo kích thước hàng đợi
& tải nạp
RED,
FRED
,...
BLUE
SFB
...
REM,
GREEN
,...
Hình 2.8 Phân loại các cơ chế quản lý hàng đợi tích cực
2.4.3 Quản lý hàng đợi tích cực trong truyền phát video trên
mạng
Trong lĩnh vực ứng dụng truyền video trên mạng, đã hình thành
hai cách tiếp cận. Các phƣơng pháp tiếp cận thứ nhất thích nghi trực
tiếp nội dung video các điều kiện mạng hiện hành tại các thiết bị đầu
cuối và đƣợc gọi là điều khiển QoS đầu cuối tới đầu cuối (QoS endto-end): Nó chủ yếu bao gồm điều khiển luồng, tránh tắc ghẽn, mã
hóa, kiểm soát lỗi và khả năng phục hồi lỗi [19] [84] [87]. Cách tiếp
cận thứ hai cung cấp hỗ trợ mạng cho video và đƣợc đặt tên là mạng
nút trung tâm [19].
Jae Chung and Mark Claypool và cộng sự đã có ý tƣởng bổ sung
thêm trọng số nhẹ, tích hợp trong giải thuật AQM quản lý hàng đợi
ƣu tiên dựa trên bộ định tuyến Internet để cải thiện đáng kể hiệu suất
của video. Đề xuất này mở rộng RED bằng cách điều chỉnh tốc độ
RED dựa trên sự hỗ trợ ba lớp ƣu tiên và áp dụng nó để MPEG
10
điều chỉnh tốc độ dựa trên các cơ chế AQM để phân lớp ƣu tiên gói
tin video. [24]
Năm 2011, Bor-Jiunn Hwang và cộng sự đã chỉ ra các thuật toán
AQM hiện đang gặp những những vấn đề sau:
(1) Hầu hết các thuật toán không thể đạt đƣợc các yêu cầu độ trễ
và thông lƣợng cùng một lúc.
(2) Các thuật toán AQM hầu nhƣ không xem xét đến các đặc
điểm luồng video mà chỉ có chính sách phân bổ băng thông công
bằng đồng nhất.
(3) Không xem xét các thuộc tính dịch vụ multicast, dẫn đến hiệu
quả băng thông thấp và hệ thống kém chất lƣợng video trung bình.
(4) Các thuật toán AQM hiện tại chỉ sử dụng điều chỉnh tốc độ
loại bỏ gói tin để khắc phục vấn đề tắc nghẽn. Tuy nhiên, bên cạnh
việc điều chỉnh tốc độ loại bỏ gói tin còn cần xem xét mức độ tắc
nghẽn, các thuật toán AQM sẽ hiệu quả hơn khi đáp ứng với lƣu
lƣợng dữ liệu khác nhau.
(5) Hầu hết các thuật toán AQM không có khả năng thích ứng,
những thuật toán phải đƣợc chỉnh sửa hay điều chỉnh một tập hợp
các thông số để đáp ứng tải trọng giao thông đa dạng và khả năng
liên kết router.
(6) Một thách thức để vƣợt qua những vấn đề tắc nghẽn khi
truyền luồng video là xem xét các kỹ thuật mã hóa video, hiệu quả
băng thông và các yêu cầu QoS đối với các luồng lƣu lƣợng khác
nhau để cho hiệu năng vƣợt trội hơn.
2.5 Kết luận chƣơng 2
Chƣơng này đã nêu tổng quan về các cơ chế quản lý hàng đợi, cơ chế
quản lý hàng đợi bị động, cơ chế quản lý hàng đợi tích cực và vai trò
của cơ chế quản lý hàng đợi tích cực trong truyền phát video trên
mạng. Cũng trong chƣơng này đã trình bày kiến trúc CQS , phân loại
các phƣơng pháp quản lý hàng đợi tích cực. Trong chƣơng tiếp theo
chúng tôi đi sâu vào nghiên cứu phân tích giải thuật quản lý hàng đợi
tích cực RED, đề xuất cải tiến RED để nâng cao chất lƣợng truyền
video trên mạng máy tính.
11
Chƣơng 3: ĐỀ XUẤT CẢI TIẾN GIẢI THUẬT QUẢN LÝ
HÀNG ĐỢI RED.
3.1. Tổng quan về giải thuật quản lý hàng đợi RED
3.1.1 Giải thuật RED
Giải thuật RED lần đầu tiên đƣợc Sally Floyd và Van Jacobson [63]
đề xuất cho chức năng quản lý hàng đợi tích cực (AQM), sau đó nó
đƣợc chuẩn hoá lại theo yêu cầu của IETF[15]. RED có khả năng
chống hiện tƣợng đồng bộ toàn cục trên toàn thể các luồng TCP, duy
trì khả năng thông qua cao cũng nhƣ độ trễ thấp cùng với cách đối xử
công bằng qua đa kết nối TCP. Một trong những lý do làm cho tỷ lệ
mất gói tin cao là do thiếu cơ chế kiểm soát và điều khiển luồng. Để
sớm phát hiện tắc nghẽn và hỗ trợ báo tắc nghẽn cho trạm nguồn, tổ
chức chuẩn IETF khuyến cáo sử dụng cơ chế quản lý hàng đợi tích
cực RED tại các bộ định tuyến trên mạng Internet.
RED tính toán kích thƣớc hàng đợi trung bình dựa trên bộ lọc
thông thấp và trung bình dịch chuyển có trọng số tăng theo hàm mũ
(EWMA- Exponential Weighted Moving Average). Kích thƣớc hàng
đợi trung bình đƣợc so sánh với hai giá trị ngƣỡng: mức ngƣỡng nhỏ
nhất minth và mức ngƣỡng lớn nhất maxth.
RED đánh dấu gói tin theo xác suất pa, với pa là một hàm tuyến
tính theo
k̂ và đƣợc xác định nhƣ sau:
k̂ min th
;
max th min th
pb
;
pa
1 count * p b
p b max p
(3.1)
(3.2)
Ở đây, RED không sử dụng kích thƣớc thực của hàng đợi để xác
định pa mà sử dụng kích thƣớc hàng đợi trung bình k̂ . Với mục đích
là để tránh sự dao động quá nhanh của hàng đợi khi có những đợt gửi
với thời gian ngắn. RED tính toán k̂ với hệ số mỗi khi có gói tin
đến theo phép gán sau: k̂ = (1 ω) k̂ + ω k (3.3)
Khi kích thƣớc hàng đợi nằm giữa mức ngƣỡng min và max, thì
mỗi gói đến sẽ đƣợc đánh dấu bằng xác suất pa, đây là một chức
năng của kích thƣớc hàng đợi trung bình. Tại mỗi thời điểm có một
12
gói bị đánh dấu và xác suất gói bị đánh dấu từ một kết nối điển hình
tỉ lệ với băng thông chia sẻ kết nối tại mỗi Bộ định tuyến.
3.1.2 Một số cải tiến của RED
3.2. Đề xuất giải thuật cải tiến ViRED
3.2.1. Ý tƣởng giải thuật
Dựa trên giải thuật RED ban đầu, chúng tôi xây dựng một hàm
tuyến tính điều chỉnh xác suất đánh dấu (loại bỏ) các gói tin dựa trên
kích thƣớc trung bình của bộ đệm tại bộ định tuyến và đặc tính của
luồng dữ liệu đến bộ đệm. Chúng tôi đề xuất tích hợp hàm tuyến tính
điều chỉnh xác suất pa đánh dấu hay (loại bỏ) gói tin tại bộ định tuyến
nhƣ sau:
If the received packet is a video
Updates the value pa = u. pa ; else pa = pa;
3.2.2. Định nghĩa hàm tuyến tính u
U là hàm tuyến tính điều chỉnh xác suất đánh dấu hay (loại bỏ)
gói tin pa. Để phân loại ƣu tiên gói tin video, hàm u đƣợc xây dựng
sao cho u[0; 1];
u (k̂ ) 1
k̂
L
(3.7)
Trong đó : L: là kích thƣớc bộ đệm tại bộ định tuyến [0, 1];
k̂ : Kích thƣớc trung bình hiện thời của bộ đệm tại bộ định tuyến.
Để hàm u nhận giá trị nhỏ hơn 1 và tỷ lệ nghịch với kích thƣớc
trung bình hiện thời của bộ đệm tại bộ định tuyến.Trong thực nghiệm
mô phỏng, chúng tôi chọn giá trị = 0.02. Ta có ( k̂ /L ) < 1 với
mọi k̂ u > 0 k̂ .
3.2.3. Cài đặt mô phỏng giải thuật
Hình 3.8 Cấu hình mạng sử dụng trong mô phỏng
13
3.2.4. Phân tích đánh giá giải thuật ViRED
+ Phân tích tỷ lệ mất gói tin
Hình 3.10. Tỷ lệ mất gói tin video
khi sử dụng RED và ViRED
+Phân tích giá trị PSNR(dB):
Hình 3.11. So sánh giá trị PSNR khi sử
dụng RED và ViRED
Sử dụng mô phỏng, chúng tôi tính toán đƣợc giá trị PSNR trung
bình nhƣ trong dạng đồ thị trên hình 4.5, chúng ta thấy giá trị
PSNR(dB) trung bình khi sử dụng giải thuật mới ViRED đã đƣợc cải
thiện tăng hơn xấp xỉ 6,9% so với khi mô phỏng sử dụng giải thuật
RED ban đầu.
Sử dụng công cụ xác suất thống kê kiểm định thang đo chủ quan
PSNR(dB) của hai giải thuật RED và ViRED khi mô phỏng video
Akio.yuv.
Kiểm định giá trị PSNR(dB) giữa RED và ViRED
PSNR RED = 29,098227,
PSNR ViRED = 31,12979
Từ đó ta tính đƣợc S’2RED = 38,41187, S’2ViRED= 41,057368
So sánh RED và ViRED, phát biểu bài toán nhƣ sau:
Giả thuyết Ho: Giá trị PSNR RED = PSNR ViRED
Đối thuyết H1: PSNR RED < PSNR ViRED
Theo lý thuyết thì: Với mức ý nghĩa α = 0,05
Khi đó Φ(zα) = α - 0,05.Tra bảng tích phân Laplace đƣợc zα = -1,65
+) Tiêu chuẩn thống kê
PSNR RED PSNR ViRED
29,098227 31,12979 = - 3,94064
Z
'2
'2
38,41187 41,057368
S RED SViRED
299
299
299
299
Rõ ràng – 3,94064 < - 1,65 vậy bác bỏ H0 . Vậy có cơ sở khẳng
định PSNR trung bình của ViRED lớn hơn RED.
Theo lý thuyết: Với mức ý nghĩa α = 0,01
Khi đó Φ(zα) = α - 0,1 .
Tra bảng tích phân Laplace đƣợc zα = -3,09
14
+) Tiêu chuẩn thống kê
Z
PSNR RED PSNR ViRED
2
S '2
S 'RED
ViRED
299
299
=
29,098227 31,12979
38,41187 41,057368
299
299
- 3,94064
Rõ ràng – 3,94064 < - 3,09 => bác bỏ H0 . Vậy có cơ sở khẳng
định PSNR trung bình của ViRED lớn hơn RED.
Đối sánh chất lƣợng video theo thang đo chất lƣợng khách quan
giữa giải thuật RED và ViRED với cấu hình mạng hình 3.6 với mẫu
video khác là foreman.yuv lấy trên thƣ viện có 400 khung hình (xem
phục lục 2) và đạt đƣợc kết quả nhƣ trong hình 3.11, kết quả cho
thấy chất lƣợng PSNR(dB) trung bình khi sử dụng giải thuật ViRED
đã tăng xấp xỉ 3,6% so với RED.
Hình 3.11. So sánh giá trị PSNR(dB), sử dụng RED và ViRED
khi thực hiện mô phỏng với tập tin video forman.yuv
3.3 Kết luận chƣơng 3. Giải thuật đề xuất ViRED cho thấy đã cải
thiện đƣợc chất lƣợng truyền video khi thực nghiệm trên NS-2. Kiểm
định bằng công cụ lý thuyết thống kê toán cho thấy cải tiến có ý
nghĩa thực tế trong cải thiện chất lƣợng truyền video trên mạng. Giải
thuật cải tiến ViRED có thể áp dụng cho các ứng dụng truyền video
trên mạng cần ƣu tiên đáp ứng chất lƣợng dịch vụ, do nó đƣợc kế
thừa các ƣu điểm của RED và đƣợc tích hợp thêm việc ƣu tiên các
luồng video. Tuy nhiên ViRED chỉ cải tiến RED theo hƣớng tích hợp
cơ chế phân loại gói tin vào trong RED mà không chỉnh sửa các
thông số cơ bản của RED nên trong các điều kiện mạng tải nặng
hoặc bùng nổ lƣu lƣợng thì ViRED mặc dù có thể duy trì việc ƣu tiên
luồng video nhƣng cũng sẽ không thể đáp ứng đƣợc trong thời gian
dài.
15
Chƣơng 4. ĐỀ XUẤT CẢI TIẾN GIẢI THUẬT QUẢN LÝ
HÀNG ĐỢI BLUE
4.1. Tổng quan giải thuật quản lý hàng đợi BLUE
4.1.1. Giải thuật BLUE
BLUE đã đƣợc Wu-chang Feng và cộng sự đề xuất năm 1999
[85]. Tác động quan trọng nhất của việc sử dụng BLUE là điều khiển
tắc nghẽn có thể đƣợc thực hiện với kích thƣớc không gian đệm tối
thiểu [17, 28, 33, 85]. Điều này làm giảm độ trễ end-to-end qua
mạng, do đó cải thiện hiệu quả của các thuật toán điều khiển tắc
nghẽn.
BLUE là một giải thuật quản lý hàng đợi tích cực để quản lý kiểm
soát tắc nghẽn dựa trên sự kiện mất gói dữ liệu và mức độ sử dụng
đƣờng truyền thay vì chiếm dụng hàng đợi. BLUE duy trì một xác
suất pm duy nhất để đánh dấu (hoặc loại bỏ) các gói tin. Khi tràn bộ
đệm, nếu hàng đợi liên tục loại các gói tin, BLUE sẽ tăng pm, do đó
tăng tốc độ gửi lại thông báo tắc nghẽn hoặc loại bỏ các gói tin.
Ngƣợc lại, nếu hàng đợi trở nên trống rỗng hoặc nếu liên kết đƣợc
nhàn rỗi, BLUE lại giảm xác suất đánh dấu (hay loại) gói tin của nó.
Dƣới đây là mã giả của giải thuật BLUE:
Dựa trên sự kiện mất
qlen > L :
if (( now -last_update) >
freeze_time ) {
pm = pm + d1;
last_update = now; }
gói tin hay
Dựa trên sự kiện đƣờng truyền rỗi
hay qlen=0:
if ((now–last_update)> freeze_time ) {
pm= pm – d2;
last_update = now; }
Đánh dấu(loại bỏ)các gói tin với xác suất pm
Hình 4.1 Mã giả giải thuật BLUE .
Các tham số sử dụng trong giải thuật:
pm: xác suất đánh dấu hoặc loại gói tin,
freeze_time: là một tham số xác định khoảng thời gian tối thiểu
giữa hai lần cập nhật liên tiếp của pm,
d1: xác định lƣợng tăng lên của pm khi hàng đợi tràn,
d2: xác định lƣợng giảm pm khi liên kết là nhàn rỗi,
now: thời điểm hiện tại,
last_update: thời điểm xảy ra lần cập nhật pm gần nhất,
16
qlen: là độ dài hàng đợi hiện tại,
L: xác định ngƣỡng cho phép gói tin đến tại hàng đợi.
4.1.2. Giải thuật Stochastic Fair Blue (SFB)
4.2. Nghiên cứu đề xuất các giải thuật cải tiến dựa trên cơ sở
hàng đợi BLUE
Phân tích sơ đồ giải thuật BLUE gốc ban đầu của W.Feng (Hình
4.1, 4.2) ta có thể thấy việc nghiên cứu điều chỉnh tham số pm, để có
thể điều chỉnh xác suất đánh dấu pm (loại bỏ) gói tin trong các giai
thuật BLUE ban đầu có thể tiến hành ở hai giai đoạn nhƣ sau:
Giai đoạn 1: tác động điều chỉnh xác suất pm ngay khi xảy ra sự
kiện mất gói tin, hoặc sự kiện đƣờng truyền không bận. Việc xử lý
tham số pm ở giai đoạn này chúng tôi gọi là tiền xử lý.
Giai đoạn 2: tác động điều chỉnh xác suất pm ở bƣớc 4, sau khi đã
xử lý cả hai sự kiện mất gói tin và đƣờng truyền không bận. Việc xử
lý tham số pm ở giai đoạn này chúng tôi gọi là hậu xử lý.
Từ đó chúng tôi đƣa ra hai nhóm giải thuật cải tiến nhƣ sau:
Nhóm I: Cải tiến kiểu tiền xử lý, (điều chỉnh xác suất pm trước)
Nhóm II: Cải tiến theo kiểu hậu xử lý, (điều chỉnh xác suất pm sau).
4.3. Đề xuất giải thuật tiền xử lý nhóm I
4.3.1. Đề xuất giải thuật tiền xử lý EBLUE
4.3.1.1. Ý tưởng cải tiến
Xây dựng hàm tuyến tính điều chỉnh xác suất loại gói.
4.3.1.2. Đề xuất xây dựng hàm tuyến tính một biến u
Để tác động vào xác suất pm khi xảy ra hiện tƣợng mất gói tin
hay (qlen > L). Chúng tôi định nghĩa hàm u nhƣ sau:
u ( x) 1
x
L
(4.1)
Trong đó: L là kích thƣớc bộ đệm, α, nhận giá trị ϵ [0, 1]; x là kích
thƣớc hiện thời của bộ đệm tính theo số gói tin.
Hàm u nhận giá trị dƣơng nhỏ hơn 1, tỉ lệ nghịch với giá trị x.
4.3.1.3. Tích hợp hàm u(x) trong giải thuật BLUE
Theo định nghĩa hàm u(x), vì
x
1 , và α đƣợc chọn nhận giá trị
L
dƣơng luôn nhỏ hơn 1 theo (4.1) ta có hàm u(x) < 1 với mọi giá trị
của x hay với mọi gói tin đến bộ đệm của bộ định tuyến.
17
4.3.2. Đề xuất giải thuật tiền xử lý BLUE-VPT
4.3.2.1. Ý tưởng giải thuật BLUE-VPT
Dựa trên cấu trúc chuỗi video MPEG, có 3 kiểu khung hình I, P,
B đƣợc mã hóa liên khung trong đó, khung hình I là quan trọng nhất
và có kích thƣớc lớn nhất. Do đặc tính của BLUE, giá trị của tham số
d1>>d2 nên đáp ứng với sự kiện mất gói tin rất nhanh. Dựa trên các
đặc tính mã hóa khung hình liên khung của MPEG chúng tôi đề xuất
cải tiến giải thuật BLUE để giảm bớt việc mất các gói tin dựa vào
phân loại các gói tin tùy theo chúng thuộc khung hình I, P, B trƣớc
khi điều chỉnh xác suất pm.
4.3.2.2 Đề xuất xây dựng hàm tuyến tính
Mô tả giải thuật: dựa trên 2 đặc tính sự kiện mất gói (qlen > L) và
sự kiện đƣờng truyền rỗi của BLUE chúng tôi đề xuất định nghĩa hai
hàm tuyến tính nhƣ sau:
Định nghĩa hàm tuyến tính u(x). Hàm u(x) đƣợc xây dựng tƣơng tự
nhƣ hàm u(x) trong công thức (4.1)
u(x) = 1-α.x/L;
Trong đó: α [0; 1]; L là kích thƣớc hàng đợi; x là kích thƣớc
hiện thời của bộ đệm.
Định nghĩa hàm tuyến tính v(y).
v(y) = 1 - β.y;
(4.2)
Trong đó: β [0; 1]; y là mức độ sử dụng đƣờng truyền và đƣợc
tính nhƣ sau:
y
byte _ departurest
Bt
byte_departurest: số bytes đƣợc truyền đi trong t giây,
B: băng thông của đƣờng truyền,
t: Thời gian truyền;
Hiển nhiên u(x), v(y) luôn nhận giá trị trong khoảng [0; 1].
Các giá trị tham số α, β của hàm u(x) , v(y) đƣợc chọn trong mô
phỏng có giá trị tƣơng ứng là 0.02 và 0.098.
Nhƣ đã trình bày ở trên, do BLUE đáp ứng rất nhanh với sự kiện
mất gói tin nên ta tích hợp hàm u(x) để ƣu tiên các gói tin thuộc
khung hình I, mỗi khi tiến hành điều chỉnh xác suất pm. Mặt khác do
d1>>d2 nên BLUE đáp ứng với sự kiện đƣờng truyền rỗi (thời điểm
18
bộ đệm trống) chậm hơn, nên sẽ tích hợp hàm v(y) để ƣu tiên các gói
tin thuộc khung hình P, B theo sự kiện đƣờng truyền rỗi. Từ đó ta có
giải thuật cải tiến BLUE-VPT.
Vì u(x) nhận giá trị [0;1] với mọi gói tin đến bộ đệm nên trong
giải thuật cải tiến sử dụng hàm điều chỉnh u(x), giá trị của xác suất
pm đƣợc cập nhật lại nhƣ sau: pm=u.pm pm , hay pm = v.pm với mọi
x, y.
Chúng tôi đã thử nghiệm đo các thông số về mức độ sử dụng
đƣờng truyền của giải thuật cải tiến BLUE-VPT và đối sánh với giải
thuật BLUE các kết quả đo mức độ sử dụng đƣờng truyền đƣợc cho
thấy mức độ sử dụng đƣờng truyền của giải thuật cải tiến đã đƣợc cải
thiện trung bình xấp xỉ 6.47% so với BLUE và 9.54% so với RED.
4.3.3. Đối sánh giải thuật cải tiến tiền xử lý nhóm I, EBLUE và
BLUE-VPT
4.3.3.1. Đối sánh trên các tham số QoS mạng
Trong phần dƣới đây chúng tôi tiến hành phân tích đối sánh hai
giải thuật tiền xử lý nhóm I trên các tham số QoS mạng:
+ Độ trễ trung bình
+ Đánh giá tỷ lệ mất gói tin
+ Thông lƣợng trung bình
+ Biến thiên trễ Jitter
4.3.3.2.Phân tích và đối sánh giải thuật nhóm I trên các tham số
đánh giá chất lượng Video
Để đánh giá chất lƣợng truyền video khi sử dụng các giải thuật
cải tiến chúng tôi sử dụng 03 tham số đo chất lƣợng video là độ mất
gói tin video, mức độ sử dụng đƣờng truyền (utilization link) và độ
đo khách quan chất lƣợng video PSNR(dB). Chúng tôi cũng sử dụng
lý thuyết thống kê để tính toán kiểm định giả thuyết trên giá trị độ
trễ trung bình và thám số chất lƣợng video khách quan PSNR(dB)
Kết luận: Trong phần này chúng tôi đã đề xuất giải pháp sử dụng
các hàm tuyến tính điều chỉnh xác suất loại bỏ gói tin dựa trên cơ
chế quản lý hàng đợi BLUE. Đó là vừa dựa trên kích thƣớc hàng đợi,
vừa dựa trên mức độ sử dụng đƣờng truyền và có tích hợp cơ chế
phân loại ƣu tiên gói tin của luồng video. Chúng tôi gọi giải thuật
hàng đợi cải tiến này là BLUE-VPT, qua các thử nghiệm mô phỏng,
đối sánh với các giải thuật quản lý hàng đợi tích cực khác là RED và
19
BLUE gốc ban đầu. Giải thuật BLUE-VPT đã cải thiện đƣợc chất
lƣợng truyền video trên mạng IP trong điều kiện mạng có đa luồng
dữ liệu tham gia và có tổn hao.
4.4. Đề xuất cải tiến giải thuật hậu xử lý nhóm II.
4.4.1. Đề xuất giải thuật VBLUE
4.4.1.1. Ý tưởng cải tiến
VBLUE tích hợp thêm cơ chế phân loại ƣu tiên các gói tin video,
khi mạng bắt đầu xảy ra mất gói tin hoặc bộ đệm bị tràn (qlen> L):
nếu gói tin là video thì thuật toán đánh dấu loại bỏ gói tin đến với
xác suất u.pm; (0 < u < 1). u là tham số ƣu tiên để làm giảm xác suất
loại bỏ gói trong trƣờng hợp gói tin đến là video. Khi lƣu lƣợng
tăng đột ngột lớn trong thời gian dài thì u có xu hƣớng tiến về 0 và
ngƣợc lại.
4.4.1.2. Cài đặt mô phỏng phân tích giải thuật VBLUE
Qua cài đặt tính toán khi thực hiện mô phỏng cho thấy cơ chế
VBLUE hiệu quả hơn cơ chế RED và xấp xỉ với BLUE trên các
thông số hiệu năng nhƣ độ trễ, và thông lƣợng phát nhƣng lại đạt
chất lƣợng cao hơn hẳn RED và BLUE về chất lƣợng video đo theo
tham số PSNR.
4.4.2. Đề xuất giải thuật BLUE-U
4.4.2.1. Ý tưởng đề xuất
Dựa trên đặc điểm của thuật toán BLUE, chúng tôi đã xây dựng
một hàm tuyến tính u điều chỉnh xác suất đánh dấu (loại bỏ) các gói
tin dựa trên các yếu tố kích thƣớc bộ đệm tại router, mức độ sử dụng
đƣờng truyền và các đặc tính trong mã hóa luồng video Mpeg.
Chúng tôi đề xuất tích hợp hàm tuyến tính hai biến để điều chỉnh
xác suất trong thuật toán BLUE khi tiến hành đánh dấu (loại bỏ) gói
tin nhƣ sau: Kiểm tra nếu gói tin đến là video cập nhật giá trị pm =
u.pm ngƣợc lại pm= pm.
Để phân loại ƣu tiên các gói tin video hàm u đƣợc xây dựng sao
cho u nhận giá trị [0, 1];
4.4.2.2. Định nghĩa hàm tuyến tính u
Định nghĩa hàm u(x,y):
X
u ( x, y) 1 . . y
L
(4.3)
20
Trong đó: L là kích thƣớc bộ đệm, α, β nhận giá trị [0, 1], x là
kích thƣớc hiện thời của bộ đệm, y là mức độ sử dụng đƣờng truyền
và đƣợc tính nhƣ sau:
y
byte _ departurest
Bt
Rõ ràng y nhận giá trị từ [0; 1], byte_departurest: số bytes đƣợc
truyền đi trong t giây, B: băng thông của đƣờng truyền, t: Thời gian
truyền;
Vấn đề đặt ra khi chọn giá trị α cho trƣớc α[0; 1] chúng ta phải
tính toán đƣợc giá trị tƣơng ứng của β trong miền [0;1] sao cho
u(x,y) nhận giá trị [0; 1] với các tham số x, y thỏa mãn điều kiện
của thuật toán BLUE.Vậy nếu chọn α=0.002 ta có thể chọn β nhận
giá trị xấp xỉ trong [0; 0,098].
Vì u(x,y) nhận giá trị [0;1] với mọi gói tin đến bộ đệm nên
trong thuật toán cải tiến sử dụng hàm điều chỉnh u(x,y), giá trị của
xác suất pm=u.pm => sẽ luôn pm x, y, do vậy thuật toán cải tiến
với hàm điều chỉnh tính toán xác suất loại gói tin sẽ luôn hội tụ đến
giá trị BLUE ban đầu, đồng thời do tích hợp cơ chế ƣu tiên các gói
tin video nên chất lƣợng luồng video đƣợc truyền qua mạng sẽ đƣợc
cải thiện đáng kể.
Sử dụng khung làm việc EVALVID với các cơ chế BLUE-U,
BLUE và RED để đánh giá chất lƣợng truyền video [13], cho thấy
thuật toán cải tiến BLUE-U đã cải thiện đƣợc chất lƣợng PSNR(dB)
trung bình so với RED là xấp xỉ 24% và BLUE là xấp xỉ 8.8%. Các
dịch vụ khác truyền trên TCP suy giảm nhƣng có thể chấp nhận
đƣợc vì các gói tin này có thể đƣợc truyền lại theo TCP và không bắt
buộc truyền trong thời gian thực.
4.5 Phân tích đối sánh giải thuật cải tiến nhóm I và II, BLUEVPT và BLUE-U
Hình 4.42. Mức độ sử dụng
đường truyền
Hình 4.43. Đối sánh giá trị PSNR(dB)
giữa BUE-U và BLUE- VPT
- Xem thêm -