Đăng ký Đăng nhập
Trang chủ 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 [...

Tài liệu 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 [tt]

.PDF
24
493
146

Mô tả:

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 Bt 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 Bt 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 -

Tài liệu liên quan