Nghiên cứu một số phương pháp lập lịch trong mạng chuyển mạch chùm quang luận án

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN HỒNG QUỐC NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP LẬP LỊCH 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 2017 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN HỒNG QUỐC NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP LẬP LỊCH TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 62.01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS. VÕ VIẾT MINH NHẬT TS. NGUYỄN HOÀNG SƠN HUẾ - NĂM 2017 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ự đồng ý 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 Nguyễn Hồng Quốc i 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, Đại 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 chân thành cảm ơn Quý Thầy Cô, Ban chủ nhiệm Khoa Tin học - Trường Đại học Sư phạm, Đạ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 học tập, nghiên cứu. Nghiên cứu sinh Nguyễn Hồng Quốc ii MỤC LỤC Lời cam đoan i Lời cảm ơn ii Mục lục iii Danh mục các từ viết tắt v Danh mục bảng biểu vii Danh mục hình vẽ viii Mở đầu 1 Chương 1. TỔNG QUAN VỀ LẬP LỊCH TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG 7 1.1 Tóm lược lịch sử phát triển của truyền thông quang .2 Các mô hình chuyển mạch quang .1 Chuyển mạch kênh quang .2 Chuyển mạch gói quang .3 Chuyển mạch chùm quang .3 Mạng chuyển mạch chùm quang .1 Kiến trúc mạng OBS .2 Các hoạt động bên trong mạng OBS .4 Lập lịch trong mạng OBS .1 Giới thiệu bài toán lập lịch .2 Một số kiến thức liên quan .3 Các giải thuật lập lịch đã công bố .4 Một số nhận xét các giải thuật lập lịch đã công bố .5 Tiểu kết Chương 1. MỘT CẢI TIẾN MÔ HÌNH KẾT HỢP LẬP LỊCH TRỰC TIẾP VỚI LẬP LỊCH LẠI VÀ PHÂN ĐOẠN CHÙM 37 2.2 Phân tích và đánh giá các giải thuật lập lịch kết hợp đã công bố .1 Giải thuật ODBR .2 Giải thuật ABR .3 Kỹ thuật phân đoạn chùm .4 Giải thuật SODBRA .5 Giải thuật PCSA .3 Giải thuật lập lịch kết hợp đề xuất iCSA .4 Mô phỏng và phân tích kết quả .5 Tiểu kết Chương 2.

MỘT SỐ CẢI TIẾN GIẢI THUẬT LẬP LỊCH NHÓM TRÊN ĐƠN KÊNH 55 3.2 Phân tích và đánh giá các giải thuật lập lịch nhóm trên đơn kênh đã công bố .1 Giải thuật OBS-GS .2 Giải thuật MWIS-OS .3 Giải thuật lập lịch nhóm trên đơn kênh đề xuất LGS và các mở rộng .1 Mô hình lập lịch nhóm trên đơn kênh .2 Giải thuật đề xuất LGS .3 Các giải thuật mở rộng đề xuất từ LGS .4 Mô phỏng và phân tích kết quả .5 Tiểu kết Chương 3. MỘT SỐ CẢI TIẾN GIẢI THUẬT LẬP LỊCH NHÓM TRÊN ĐA KÊNH 72 4.2 Phân tích và đánh giá các giải thuật lập lịch nhóm trên đa kênh đã công bố .1 Nhóm các giải thuật lập lịch heuristic .2 Nhóm các giải thuật lập lịch tối ưu .3 Các giải thuật lập lịch nhóm đề xuất trên đa kênh .1 Giải thuật lập lịch nhóm tối ưu OPT-GS .2 Giải thuật lập lịch nhóm heuristic LGS-MC .3 Giải thuật lập lịch nhóm heuristic MWC-GS .4 Mô phỏng và phân tích kết quả .5 Tiểu kết Chương 4. 101 KẾT LUẬN 102 DANH MỤC CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN LUẬN ÁN 104 TÀI LIỆU THAM KHẢO 105 iv DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Dạng đầy đủ Diễn giải ý nghĩa ADM Add-Drop Multiplexer Bộ thêm/trích kênh AON All-Optical Network Mạng toàn quang ATM Asynchronous Transfer Mode Chế độ truyền tải không đồng bộ BHP Burst Header Packet Gói điều khiển CWDM Coarse Wavelength Division Mul- Ghép kênh phân chia bước sóng tiplexing thô DWA Dynamic Wavelength Allocation Phân bổ bước sóng động DWDM Density Wavelength Division Ghép kênh phân chia bước sóng Multiplexing mật độ cao FDL Fiber Delay Line Đường trễ quang FDM Frequency Division Multiplexing Ghép kênh phân chia tần số GMPLS Generalized Multiprotocol Label Chuyển mạch nhãn đa giao thức Switching suy rộng 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 thời gian đặt trước tức thời LAUT Latest Available Unscheduled Thời điểm chưa được lập lịch sau Time cùng nhất LRWC Limited-Range Wavelength Con- Bộ chuyển đổi bước sóng có phạm verter vi giới hạn MPLS MultiProtocol Label Switching Chuyển mạch nhãn đa giao thức MWC Optical/Electronic/Optical Chuyển đổi quang-điện-quang MWC Maximum Weight Clipue Clique có tổng trọng số lớn nhất O/E/O Optical/Electronic/Optical Chuyển đổi quang-điện-quang OADM Optical Add-Drop Multiplexer Bộ thêm/trích kênh quang OBS Optical Burst Switching Chuyển mạch chùm quang OCS Optical Circuit Switching Chuyển mạch kênh quang OEO Optical-Electrical-Optical con- Chuyển đổi quang-điện-quang version v Viết tắt Dạng đầy đủ Diễn giải ý nghĩa OPS Optical Packet Switching Chuyển mạch gói quang OTN Optical Transport Network Mạng truyền tải quang OTDM Optical Time Division Multiplex- Ghép kênh quang phân chia thời ing gian OXC Optical Cross Connect Chuyển mạch quang QoS Quality of Service Chất lượng dịch vụ ROADM Reconfigurable Optical Add-Drop Bộ thêm/trích kênh quang có thể Multiplexer cấu hình lại RTT Round-Trip Time Thời gian khứ hồi RAM Random Access Memory Bộ nhớ truy cập ngẫu nhiên RWA Routing and Wavelength Alloca- Định tuyến và cấp phát bước sóng tion SCU Switching Control Unit Đơn vị điều khiển chuyển mạch SDH Synchronous Digital Hierarchy Hệ phân cấp số đồng bộ SDM Space Division Multiplexing Ghép kênh phân chia không gian SIR Source Initiated Reservation Đặt tài nguyên từ nguồn SONET Synchronous Optical Network Mạng quang đồng bộ SPL Share-Per-Link Chia sẻ trên mỗi liên kết SPN Share-Per-Node Chia sẻ trên mỗi nút WADM Wavelength Add-Drop Multi- Bộ thêm/trích bước sóng plexer WC Wavelength Converters Bộ chuyển đổi bước sóng WDM Wavelength Division Multiplex- Ghép kênh phân chia bước sóng ing WR Wavelength Router Định tuyến bước sóng WRN Wavelength Routed Network Mạng định tuyến bước sóng WXC Wavelength Cross-Connect Chuyển mạch bước sóng vi DANH MỤC BẢNG BIỂU 1.1 So sánh chuyển mạch chùm quang với chuyển mạch kênh quang và chuyển mạch gói quang .1 Thống kê số chùm được gỡ ra và lập lịch lại thành công của giải thuật GreedyOPT. 99 vii DANH MỤC HÌNH VẼ 1.1 Kiến trúc mạng chuyển mạch kênh quang .2 Kiến trúc mạng OBS và chức năng của các nút mạng .3 Cấu trúc nút biên vào OBS .4 Cấu trúc nút lõi OBS .5 Tập hợp theo ngưỡng thời gian .6 Tập hợp theo ngưỡng kích thước (số gói tin tối đa) .7 Ảnh hưởng của phương pháp tập hợp chùm theo ngưỡng thời gian và ngưỡng độ dài đối với kích thước chùm được sinh ra .8 Đồ thị khoảng G được xây dựng từ tập các khoảng thời gian chồng lấp nhau .9 Đồ thị khoảng G được xây dựng từ tập các khoảng thời gian không chồng lấp nhau .10 Mô tả các giải thuật lập lịch trực tiếp .11 Ví dụ so sánh hiệu quả giữa lập lịch trực tiếp và lập lịch nhóm: (a) các gói điều khiển và chùm đến trong khe thời gian τ , (b) kết quả của lập lịch trực tiếp và (c) kết quả của lập lịch nhóm dựa trên tối đa tổng số chùm được lập lịch và (d)dựa trên tối đa tổng độ dài của các chùm được lập lịch .12 Phân loại các giải thuật lập lịch nhóm đã được công bố .13 Mô tả giải pháp chuyển đổi bước sóng w1 qua w2 .14 Mô tả giải pháp định tuyến lệch hướng .1 Một ví dụ về lập lịch lại của giải thuật ODBR .2 Một ví dụ cơ chế hoạt động của giải thuật lập lịch lại ABR .3 Phân đoạn chùm và cấu trúc bên trong của header của đoạn .4 Trong trường hợp chùm tranh chấp bị phân đoạn, có 2 khá năng xảy ra: (a) loại bỏ đoạn đuôi và (b) loại bỏ đoạn đầu của chùm tranh chấp .5 Ví dụ một chùm đến ub yêu cầu lập lịch trên 3 kênh ra .6 Ví dụ về một trường hợp giải thuật ODBR không thực hiện được .7 Mô hình mạng mô phỏng NSFNET .8 So sánh xác suất mất gói tin của LAUC và BFVF .9 So sánh xác suất mất gói tin của ODBR và ABR .10 So sánh số chùm phải lập lịch lại giữa ODBR và ABR .11 So sánh xác suất mất gói tin của iCSA so với ODBR và ABR .12 So sánh số chùm lập lịch lại của iCSA so với ODBR và ABR .13 So sánh xác suất mất gói tin của iCSA so với PCSA và SODBRA .14 So sánh số chùm lập lịch lại của iCSA so với SODBRA và PCSA .15 So sánh số chùm phân đoạn của iCSA so với SODBRA và PCSA .2 Các gói điều khiển đến trong khe thời gian τ , tương ứng với thứ tự đến của các chùm .3 (a)Đồ thị khoảng được xây dựng tương ứng trạng thái các chùm đến và (b)Kết quả tìm tập các tập độc lập cực đại của giải thuật OBS-GS .4 Kết quả tìm tập các tập độc lập cực đại của giải thuật MWIS-OS .5 So sánh xác suất mất gói tin của OBS-GS và MWIS-OS .6 Mô hình hoạt động của lập lịch nhóm được đề xuất .7 Ví dụ Các gói điều khiển đến trong thời gian τ và thứ tự đến của các chùm .8 (a) Thứ tự các chùm sau khi sắp xếp theo thời điểm kết thúc và (b) cách tính index .9 Khe thời gian lập lịch nhóm τ được điều chỉnh nghịch biến với tốc độ của luồng các chùm đến .10 Mô hình mạng mô phỏng Dumbbell .11 So sánh xác suất mất gói tin giữa LAUC-VF và LGS .12 So sánh xác suất mất gói tin giữa OBS-GS, MWIS-OS, LGS và LGS-VF 68 3.13 So sánh thông lượng của OBS-GS, MWIS-OS và LGS-VF .14 So sánh xác suất mất gói tin giữa LGS-VF và LAGS-VF .