Luận án: Điều khiển công bằng luồng trong mạng chuyển mạch chùm quang

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ VĂN HÒA ĐIỀU KHIỂN CÔNG BẰNG LUỒNG TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HUẾ - NĂM 2019 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC LÊ VĂN HÒA ĐIỀU KHIỂN CÔNG BẰNG LUỒNG TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 9480101 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: 1. VÕ VIẾT MINH NHẬT 2. NGUYỄN HOÀNG SƠN HUẾ - NĂM 2019 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện dưới sự hướng dẫn của PGS. Võ Viết Minh Nhật và TS.

Những nội dung trong các công trình đã được công bố chung với các tác giả khác đã được sự chấp thuận của đồng tác giả khi đưa vào luận án. Các số liệu và kết quả nghiên cứu được trình bày trong luận án là trung thực, khách quan và chưa được công bố bởi tác giả nào trong bất kỳ công trình nào khác. Nghiên cứu sinh Lê Văn Hòa ii LỜI CẢM ƠN Trước hết tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến PGS. Võ Viết Minh Nhật và TS.

Nguyễn Hoàng Sơn là những người Thầy đã tận tình hướng dẫn chỉ bảo, động viên và giúp đỡ để tôi có thể hoàn thành được luận án này. Tôi xin trân trọng cảm ơn sự giúp đỡ của Quý Thầy Cô trong Khoa Công nghệ Thông tin - Trường Đại học Khoa học Huế đã quan tâm, giúp đỡ, hướng dẫn trong suốt quá trình học tập. Tôi xin trân trọng cảm ơn Quý Thầy Cô, Ban chủ nhiệm Khoa Du lịch - Đại học Huế đã tạo điều kiện thuận lợi trong công tác để tôi có đủ thời gian hoàn thành luận án này. Tôi xin cảm ơn Quý Thầy Cô, cán bộ quản lý Phòng Đào tạo Sau đại học – Trường Đại học Khoa học, Đại học Huế đã giúp đỡ tôi hoàn thành kế hoạch học tập.

Cuối cùng tôi xin chân thành cảm ơn các bạn đồng nghiệp, người thân trong gia đình luôn động viên, giúp đỡ tôi về mọi mặt trong suốt quá trình nghiên cứu, học tập. Nghiên cứu sinh Lê Văn Hòa iii MỤC LỤC MỤC LỤC.iv DANH MỤC CÁC TỪ VIẾT TẮT.vi CÁC KÝ HIỆU TOÁN HỌC ĐƯỢC SỬ DỤNG.x DANH MỤC CÁC HÌNH VẼ.xiii DANH MỤC CÁC BẢNG. xvi MỞ ĐẦU. TỔNG QUAN VỀ CÔNG BẰNG TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG.1 Các mô hình chuyển mạch trong truyền thông quang.2 Nguyên tắc hoạt động của mạng OBS.3 Các hoạt động bên trong mạng OBS.1 Tập hợp chùm.3 Lập lịch chùm.4 Xử lý tranh chấp chùm.4 Vấn đề công bằng trong mạng OBS.1 Khái niệm và phân loại công bằng trong mạng OBS.2 Công bằng độ trễ.3 Công bằng thông lượng.4 Công bằng khoảng cách.5 Kết hợp công bằng thông lượng và công bằng khoảng cách.6 Đánh giá các giải pháp công bằng tại nút biên mạng OBS.5 Các mục tiêu nghiên cứu của luận án.6 Tiểu kết Chương 1.

TẬP HỢP CHÙM GIẢM ĐỘ TRỄ VÀ CÔNG BẰNG ĐỘ TRỄ 31 2.1 Mô hình tập hợp chùm giảm độ trễ.1 Vấn đề độ trễ trong hoạt động tập hợp chùm.2 Các công trình nghiên cứu liên quan.3 Phương pháp tập hợp chùm giảm độ trễ iBADR.4 Phương pháp tập hợp chùm giảm độ trễ OBADR.5 Ảnh hưởng của trọng số α đến OBADR.6 Ảnh hưởng của OBADR đến hoạt động lập lịch chùm.2 Mô hình tập hợp chùm công bằng độ trễ.1 Các công trình nghiên cứu liên quan.2 Phương pháp tập hợp chùm công bằng độ trễ BADF.3 Tiểu kết Chương 2. CÔNG BẰNG THÔNG LƯỢNG DỰA TRÊN CẤP PHÁT BĂNG THÔNG VÀ ĐẮP CHÙM 73 3.1 Mô hình cấp phát băng thông công bằng dựa trên thông lượng.1 Giới thiệu về cấp phát băng thông công bằng.2 Các công trình nghiên cứu liên quan.3Phương pháp cấp phát băng thông công bằng dựa trên thông lượng TFBA77 3.4 Phân tích ảnh hưởng của TFBA đến việc lập lịch tại liên kết ra.2 Mô hình đắp chùm hiệu quả băng thông và công bằng thông lượng.1 Các công trình nghiên cứu liên quan.2 Phương pháp đắp chùm.3 Tiểu kết Chương 3.99 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN ÁN.100 DANH MỤC CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN LUẬN ÁN.101 TÀI LIỆU THAM KHẢO.102 v DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Thuật ngữ tiếng Anh Diễn giải ý nghĩa ACK Acknowledgement, Gói điều khiển thông báo việc truyền thông/lập lịch thành công NACK Negative Acknowledgement Gói điều khiển thông báo việc truyền thông/lập lịch thất bại AON All-Optical Network Mạng toàn quang ATM Asynchronous Transfer Mode Kiểu truyền thông không đồng bộ BADF Burst Assembly for Delay Tập hợp chùm công bằng độ trễ Fairness BADR- BADR with Extra Assembly Tập hợp chùm giảm độ trễ với thời EAT* Time gian tập hợp chùm mở rộng BASTP* Burst Assembly based on Size Tập hợp chùm giảm độ trễ dựa trên and Time Prediction dự đoán kích thước và thời gian tập hợp BCP Burst Control Packet Gói điều khiển chùm BLD burst length-based differentiation Phân biệt dựa vào kích thước chùm DFI Delay Fairness Index Chỉ số công bằng độ trễ DWDM Density Wavelength Division Ghép kênh phân chia bước sóng mật Multiplexing độ cao FDL Fiber Delay Line Đường trễ quang FDM Frequency Division Multiplexing Ghép kênh phân chia tần số FPP Fair Prioritized Preemption Điều khiển dựa trên ưu tiên công bằng GMPLS Generalized Multiprotocol Label Chuyển mạch nhãn đa giao thức suy Switching rộng vi Từ viết tắt Thuật ngữ tiếng Anh Diễn giải ý nghĩa HBP Hop Based Preemption Điều khiển dựa trên số chặng Hop-FCR Hop-by-hop routing using Định tuyến từng chặng với đặt trước Forward Channel Reservation kênh theo hướng truyền đi Hop-LC Hop-by-hop routing using Link Định tuyến từng chặng dựa trên số Connectivity kết nối của liên kết ra Hop-N- Hop-by-hop routing using Định tuyến từng chặng với đặt trước FCR Neighborhood Forward Channel kênh theo hướng truyền về Reservation iBADR improved Burst Assembly for Tập hợp chùm giảm độ trễ cải tiến Delay Reduction IE-BADR* Immediate Estimation-based Tập hợp chùm giảm độ trễ dựa trên BADR ước tính nhanh IP Internet Protocol Giao thức mạng Internet JET Just Enough Time Giao thức báo hiệu với thời gian đặt trước tài nguyên vừa đủ JIT Just In Time Giao thức báo hiệu với đặt trước tài nguyên ngay lập tức JK- Jacobson/Karels algorithm-based Tập hợp chùm giảm độ trễ dựa trên BADR* BADR giải thuật Jacobson/Karels LAUT Latest Available Unscheduled Thời điểm chưa được lập lịch sau Time cùng nhất LSOS Link State based Offset Selection Chọn thời gian offset dựa trên trạng thái liên kết MGDP Monitoring Group Drop Xác suất đánh rơi theo nhóm Probability MMFP Max-Min Fairness Preemption Ưu tiên dựa trên công bằng max- vi Từ viết tắt Thuật ngữ tiếng Anh Diễn giải ý nghĩa min MTBA- Mixed-Threshold Burst Assembly Tập hợp chùm giảm độ trễ dựa trên TP* based on Traffic Prediction dự đoán lưu lượng O/E/O Optical/Electronic/Optical Chuyển đổi quang - điện - quang OBADR Optimal Burst Assembly for Tập hợp chùm giảm độ trễ tối ưu Delay Reduction OBS Optical Burst Switching Chuyển mạch chùm quang OCS Optical Circuit Switching Chuyển mạch kênh quang OPS Optical Packet Switching Chuyển mạch gói quang OTD Offset Time based Differentiation Phân biệt dựa trên thời gian bù đắp OXC Optical Cross Connect Thiết bị chuyển mạch quang POQA* Prediction and Offset QoS Tập hợp chùm hỗ trợ QoS dựa trên Assembly thời gian offset và dự đoán QoS Quality of Service Chất lượng dịch vụ QDBAP QoS Differentiation Burst Tập hợp chùm phân biệt chất lượng Assembly with Padding dịch vụ kết hợp với đắp chùm RCBP Resource Consumption Based Ưu tiên dựa trên tiêu thụ tài nguyên Preemptive RDFP Rate and Distance Fairness Ưu tiên công bằng tốc độ và khoảng Preemption cách RTT Round-Trip Time Thời gian khứ hồi RFP Rate Fairness Preemption Ưu tiên công bằng tốc độ TFBA Throughput-based Fair Bandwith Cấp phát băng thông công bằng dựa Allocation trên thông lượng TFI Throuphut Fairness Index Chỉ số công bằng thông lượng vi Từ viết tắt Thuật ngữ tiếng Anh Diễn giải ý nghĩa TW- Time Windows based Trung bình dịch chuyển có trọng số EWMA Exponentially Weighted Moving dựa trên cửa sổ thời gian Average WDM Wavelength Division Ghép kênh phân chia bước sóng Multiplexing * Các phương pháp được luận án đặt tên để dễ dàng cho việc tham chiếu. ix CÁC KÝ HIỆU TOÁN HỌC ĐƯỢC SỬ DỤNG Ký hiệu Ý nghĩa ABi Băng thông cung cấp cho luồng i ATi Thông lượng thực tế của luồng i Bmin Ngưỡng kích thước chùm tối thiểu B(i) Kích thước hàng đợi i D(i) Độ trễ gói tin trong hàng đợi i Ei Tải hiệu quả của kết nối i Fi Tỉ lệ cấp phát băng thông công bằng cho hàng đợi i K Tổng số luồng (kết nối) L Độ dài chùm hoàn thành của lần tập hợp chùm hiện thời Le Độ dài chùm ước tính của lần tập hợp chùm hiện thời Lw Độ dài chùm trong khoảng thời gian ước tính Lw(i) Độ dài chùm trong khoảng thời gian ước tính của hàng đợi i Lmin Ngưỡng độ dài chùm tối thiểu Lmax Ngưỡng độ dài chùm tối đa L(i) Độ dài chùm hoàn thành của hàng đợi i 𝐿𝑒(𝑖) Độ dài chùm ước tính của hàng đợi i Lj Độ dài chùm hoàn thành ở lần tập hợp thứ j 𝐿𝑗𝑒 Độ dài chùm ước tính ở lần tập hợp thứ j M Số lần tập hợp chùm sau cùng nhất PiU Xác suất mất chùm của phần luồng tốt của luồng i PiO Xác suất mất chùm của phần luồng xấu của luồng i PU Tổng xác suất mất chùm của phần luồng tốt x Ký hiệu Ý nghĩa PO Tổng xác suất mất chùm của phần luồng xấu P Tổng xác suất mất chùm của liên kết ra Pi Tổng xác suất mất chùm của luồng i Q Tổng số hàng đợi RE Lỗi ước tính trong lần tập hợp chùm hiện thời RE Lỗi ước tính trung bình trong các lần tập hợp chùm t1 Thời điểm gửi gói điều khiển t1(i) Thời điểm gửi gói điều khiển của hàng đợi i t2 Thời điểm gửi chùm dữ liệu t2(i) Thời điểm gửi chùm dữ liệu của hàng đợi i Ta Ngưỡng thời gian tập hợp chùm; Ta cũng là độ trễ tập hợp chùm (thời gian mà các gói tin đợi trong hàng đợi trước khi được gộp vào một chùm) Ta(i) Ngưỡng thời gian tập hợp chùm của hàng đợi i To Thời gian offset (offset time) To(i) Thời gian offset của hàng đợi i Te(i) Ngưỡng thời gian ước tính trên hàng đợi i Tj Ngưỡng thời gian tập hợp chùm thứ j trong mô hình tập hợp chùm giảm độ trễ BASTP Tw Cửa sổ thời gian ước tính W Tổng số bước sóng của liên kết ra i Tốc độ đến của luồng i U Tốc độ đến của phần luồng tốt O Tốc độ đến của phần luồng xấu cur Tốc độ gói tin đến của lần tập hợp chùm hiện thời xi Ký hiệu Ý nghĩa prev Tốc độ gói tin đến của lần tập hợp chùm trước đó.