Luận án 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

M Đ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. TS. Võ Viết Minh Nhật và TS. Nguyễn Hoàng Sơn. 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. TS. 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 . . . . . . . . . . . 7 1.2 Các mô hình chuyển mạch quang . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Chuyển mạch kênh quang . . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Chuyển mạch gói quang . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3 Chuyển mạch chùm quang . . . . . . . . . . . . . . . . . . . . . 11 1.3 Mạng chuyển mạch chùm quang . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Kiến trúc mạng OBS . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.2 Các hoạt động bên trong mạng OBS . . . . . . . . . . . . . . . 17 1.4 Lập lịch trong mạng OBS . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4.1 Giới thiệu bài toán lập lịch . . . . . . . . . . . . . . . . . . . . . 22 1.4.2 Một số kiến thức liên quan . . . . . . . . . . . . . . . . . . . . . 23 1.4.3 Các giải thuật lập lịch đã công bố . . . . . . . . . . . . . . . . . 26 1.4.4 Một số nhận xét các giải thuật lập lịch đã công bố . . . . . . . 35 1.5 Tiểu kết Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chương 2. 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.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ố . . . . 37 2.2.1 Giải thuật ODBR . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.2.2 Giải thuật ABR . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.3 Kỹ thuật phân đoạn chùm . . . . . . . . . . . . . . . . . . . . . 40 2.2.4 Giải thuật SODBRA . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.5 Giải thuật PCSA . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3 Giải thuật lập lịch kết hợp đề xuất iCSA . . . . . . . . . . . . . . . . . 44 2.4 Mô phỏng và phân tích kết quả . . . . . . . . . . . . . . . . . . . . . . 48 iii 2.5 Tiểu kết Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Chương 3. MỘT SỐ CẢI TIẾN GIẢI THUẬT LẬP LỊCH NHÓM TRÊN ĐƠN KÊNH 55 3.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.1 Giải thuật OBS-GS . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.2 Giải thuật MWIS-OS . . . . . . . . . . . . . . . . . . . . . . . . 57 3.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 . 59 3.3.1 Mô hình lập lịch nhóm trên đơn kênh . . . . . . . . . . . . . . . 59 3.3.2 Giải thuật đề xuất LGS . . . . . . . . . . . . . . . . . . . . . . 60 3.3.3 Các giải thuật mở rộng đề xuất từ LGS . . . . . . . . . . . . . . 63 3.4 Mô phỏng và phân tích kết quả . . . . . . . . . . . . . . . . . . . . . . 67 3.5 Tiểu kết Chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Chương 4. MỘT SỐ CẢI TIẾN GIẢI THUẬT LẬP LỊCH NHÓM TRÊN ĐA KÊNH 72 4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.2.1 Nhóm các giải thuật lập lịch heuristic . . . . . . . . . . . . . . . 73 4.2.2 Nhóm các giải thuật lập lịch tối ưu . . . . . . . . . . . . . . . . 77 4.3 Các giải thuật lập lịch nhóm đề xuất trên đa kênh . . . . . . . . . . . . 81 4.3.1 Giải thuật lập lịch nhóm tối ưu OPT-GS . . . . . . . . . . . . 81 4.3.2 Giải thuật lập lịch nhóm heuristic LGS-MC . . . . . . . . . . . 86 4.3.3 Giải thuật lập lịch nhóm heuristic MWC-GS . . . . . . . . . . . 88 4.4 Mô phỏng và phân tích kết quả . . . . . . . . . . . . . . . . . . . . . . 96 4.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- tiplexing Ghép kênh phân chia bước sóng thô DWA Dynamic Wavelength Allocation Phân bổ bước sóng động DWDM Density Wavelength Division Multiplexing Ghép kênh phân chia bước sóng 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 Switching Chuyển mạch nhãn đa giao thức 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 Time Thời điểm chưa được lập lịch sau cùng nhất LRWC Limited-Range Wavelength Con- verter Bộ chuyển đổi bước sóng có phạm 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- version Chuyển đổi quang-điện-quang 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- ing Ghép kênh quang phân chia thời 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 Multiplexer Bộ thêm/trích kênh quang có thể 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- tion Định tuyến và cấp phát bước sóng 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- plexer Bộ thêm/trích bước sóng WC Wavelength Converters Bộ chuyển đổi bước sóng WDM Wavelength Division Multiplex- ing Ghép kênh phân chia bước sóng 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.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 . . . . . . . . . . . . . . . . . 10 1.2 Kiến trúc mạng OBS và chức năng của các nút mạng . . . . . . . . . . 15 1.3 Cấu trúc nút biên vào OBS . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Cấu trúc nút lõi OBS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.5 Tập hợp theo ngưỡng thời gian . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Tập hợp theo ngưỡng kích thước (số gói tin tối đa) . . . . . . . . . . . . 18 1.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 . . . . . . . . . . . 19 1.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.10 Mô tả các giải thuật lập lịch trực tiếp . . . . . . . . . . . . . . . . . . . 26 1.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.12 Phân loại các giải thuật lập lịch nhóm đã được công bố . . . . . . . . . 32 1.13 Mô tả giải pháp chuyển đổi bước sóng w1 qua w2 . . . . . . . . . . . . . 33 1.14 Mô tả giải pháp định tuyến lệch hướng . . . . . . . . . . . . . . . . . . 34 2.1 Một ví dụ về lập lịch lại của giải thuật ODBR . . . . . . . . . . . . . . 38 2.2 Một ví dụ cơ chế hoạt động của giải thuật lập lịch lại ABR . . . . . . . 40 2.3 Phân đoạn chùm và cấu trúc bên trong của header của đoạn . . . . . . 41 2.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 . . . 41 2.5 Ví dụ một chùm đến ub yêu cầu lập lịch trên 3 kênh ra . . . . . . . . . 43 2.6 Ví dụ về một trường hợp giải thuật ODBR không thực hiện được . . . 44 2.7 Mô hình mạng mô phỏng NSFNET . . . . . . . . . . . . . . . . . . . . 48 2.8 So sánh xác suất mất gói tin của LAUC và BFVF . . . . . . . . . . . . 49 2.9 So sánh xác suất mất gói tin của ODBR và ABR . . . . . . . . . . . . 50 2.10 So sánh số chùm phải lập lịch lại giữa ODBR và ABR . . . . . . . . . 50 2.11 So sánh xác suất mất gói tin của iCSA so với ODBR và ABR . . . . . 51 viii 2.12 So sánh số chùm lập lịch lại của iCSA so với ODBR và ABR . . . . . 51 2.13 So sánh xác suất mất gói tin của iCSA so với PCSA và SODBRA . . . 52 2.14 So sánh số chùm lập lịch lại của iCSA so với SODBRA và PCSA . . . 53 2.15 So sánh số chùm phân đoạn của iCSA so với SODBRA và PCSA . . . 53 3.1 (a) Mô tả hoạt động lập lịch nhóm trên đơn kênh và (b)đa kênh . . . . 55 3.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.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 . . . 57 3.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 . . . 58 3.5 So sánh xác suất mất gói tin của OBS-GS và MWIS-OS . . . . . . . . 58 3.6 Mô hình hoạt động của lập lịch nhóm được đề xuất . . . . . . . . . . . 59 3.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.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 . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.10 Mô hình mạng mô phỏng Dumbbell . . . . . . . . . . . . . . . . . . . . 67 3.11 So sánh xác suất mất gói tin giữa LAUC-VF và LGS . . . . . . . . . . 68 3.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 . . . . . . . 69 3.14 So sánh xác suất mất gói tin giữa LGS-VF và LAGS-VF . . . . . . . 69 3.15 Phân bố độ rộng khe thời gian τ của MWIS-OS và LAGS-VF trong 300 lần lập lịch nhóm liên tiếp . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.16 So sánh thời gian chờ trung bình (của từng 500 khe liên tiếp) của MWIS- OS và LAGS-VF (trong 7500 lần lập lịch nhóm liên tiếp) . . . . . . . 70 4.1 (a) Ví dụ tình trạng các gói điều khiển đến lập lịch cho các chùm trong mỗi khe thời gian τ , và (b) kết quả lập lịch của giải thuật SSF . . . . . 73 4.2 (a) Ví dụ tình trạng các gói điều khiển đến lập lịch cho các chùm trong mỗi khe thời gian τ , và (b) kết quả lập lịch của giải thuật LIF . . . . . 74 4.3 Đồ thị khoảng được xây dựng từ trạng thái các chùm đến ở Hình 4.1(a) 75 4.4 Ví dụ 3 chùm đến yêu cầu lập lịch trên 2 kênh dữ liệu ra . . . . . . . . 78 4.5 Đồ thị khoảng được xây dựng từ trạng thái các chùm đến và các chùm đã lập lịch trong Hình 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.6 Kết quả các clique cực đại được tìm thấy từ đồ thị khoảng trong Hình 4.5 79 4.7 Đồ thị luồng được xây dựng từ các clique cực đại trong Hình 4.6 . . . . 80 ix 4.8 Ví dụ 6 chùm đến yêu cầu lập lịch trên hai kênh ra . . . . . . . . . . . 80 4.9 (a) Một ví dụ về tình trạng các chùm đến yêu cầu lập lịch hai kênh dữ liệu ra và (b) kết quả lập lịch tối ưu các chùm trên hai kênh ra . . . . . 84 4.10 Đơn đồ thị có hướng có trọng số được xây dựng từ tập các chùm đến lập lịch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.11 (a) Ví dụ về các chùm đến và (b) kết quả lập lịch tối ưu trên 2 kênh . . 89 4.12 (a)Đồ thị khoảng biểu diễn các khả năng lập lịch của các chùm đến trong Hình 4.11a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.13 (b)MWC được tìm thấy tương ứng với kết quả lập lịch tối ưu trong Hình 4.11b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.14 (a)Ví dụ về các chùm đến và (b) kết quả lập lịch tối ưu có lấp đầy khoảng trống trên 2 kênh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.15 (a) Đồ thị khoảng biểu diễn các khả năng lập lịch có lấp đầy khoảng trống của các chùm đến trong Hình 4.14a và (b) Clique được tìm thấy tương ứng với kết quả lập lịch trong Hình 4.14b . . . . . . . . . . . . . 95 4.16 So sánh xác suất mất gói tin của LGS-MC, MWC-GS với các giải thuật heuristic trên mô hình mạng Dumbbell . . . . . . . . . . . . . . . . . . 97 4.17 So sánh xác suất mất gói tin của LGS-MC, MWC-GS với các giải thuật heuristic trên mô hình mạng NSFNET-14 nút . . . . . . . . . . . . . . 97 4.18 So sánh xác suất mất gói tin của LGS-MC, MWC-GS với GreedyOPT trên mô hình mạng Dumbbell . . . . . . . . . . . . . . . . . . . . . . . 98 4.19 So sánh xác suất mất gói tin của LGS-MC, MWC-GS với GreedyOPT trên mô hình mạng NSFNET-14 nút . . . . . . . . . . . . . . . . . . . 98 4.20 So sánh xác suất mất gói tin của MWC-VF-GS, OPT-GS với BATCHOPT trên mô hình mạng Dumbbell . . . . . . . . . . . . . . . . . . . . . . . 100 4.21 So sánh xác suất mất gói tin của MWC-VF-GS, OPT-GS với BATCHOPT trên mô hình mạng NSFNET-14 nút . . . . . . . . . . . . . . . . . . . 100 4.22 So sánh ảnh hưởng của kích thước khe thời gian τ đến hiệu quả lập lịch nhóm của MWC-VF-GS, OPT-GS với BATCHOPT . . . . . . . . . . . 101 x MỞ ĐẦU 1. Tính cấp thiết của đề tài Tốc độ phát triển nhanh của Internet trong những năm gần đây, cùng với sự bùng nổ của các loại hình dịch vụ truyền thông, đã làm gia tăng không ngừng nhu cầu về băng thông truyền thông. Điều này đã đặt ra một thách thức mới trong việc tìm kiếm công nghệ truyền thông phù hợp nhằm nâng cao khả năng vận chuyển của mạng thế hệ mới. Mạng sợi quang cùng với sự phát triển của công nghệ ghép kênh bước sóng (Wavelength Division Multiplexing), đã mang đến một giải pháp hoàn hảo đáp ứng được nhu cầu băng thông bùng nổ của Internet trong tương lai. Mạng sợi quang từ khi ra đời vào thập niên 90 cho đến nay, đã trải qua nhiều thế hệ phát triển [46], [64], [27], [24], [31], [12]: từ những mô hình định tuyến bước sóng (Wavelength-Routed) ban đầu dựa trên những đường quang (lightpath) đầu-cuối dành riêng, cho đến các mô hình chuyển mạch gói quang (Optical Packet Switching) được đề xuất gần đây, với ý tưởng xuất phát từ các mô hình mạng chuyển mạch gói điện tử. Tuy nhiên với một số hạn chế về công nghệ, như chưa thể sản xuất các bộ đệm quang (tương tự bộ nhớ RAM trong môi trường điện tử) hay các chuyển mạch ở tốc độ nano giây [8] [12], mô hình chuyển mạch gói quang chưa thể trở thành hiện thực. Một giải pháp thỏa hiệp được đề xuất là chuyển mạch chùm quang (Optical Burst Switching) đã mở ra một hướng nghiên cứu mới và được xem là công nghệ hứa hẹn cho mạng Internet thế hệ tiếp theo. Một đặc trưng tiêu biểu của mạng chuyển mạch chùm quang (mạng OBS) là phần (gói) điều khiển (Burst Header Packet) được tách rời với phần (chùm) dữ liệu (Data Burst). Nói một cách khác, để thực hiện việc truyền một chùm vào trong mạng lõi, gói điều khiển BHP được tạo ra và được gửi đi trước một khoảng thời gian offset(offset-time). Thời gian offset này phải được tính toán đủ để đặt trước tài nguyên và cấu hình các chuyển mạch tại các nút trung gian dọc theo hành trình của chùm quang từ nguồn đến đích. Thêm vào đó, mạng 1 OBS dành riêng một số kênh (bước sóng), được gọi là kênh điều khiển cho việc truyền gói điều khiển BHP, trong khi các kênh còn lại được dùng cho việc truyền chùm dữ liệu, nên được gọi là kênh dữ liệu. Như vậy việc truyền gói điều khiển BHP tách rời hoàn toàn với truyền dữ liệu về mặt không gian (trên kênh truyền khác) và về mặt thời gian (gửi đi trước một khoảng thời gian offset). Với cách truyền dữ liệu như vậy, rõ ràng mạng OBS không cần đến các bộ đệm quang để lưu tạm các chùm dữ liệu trong khi chờ đợi việc xử lý chuyển mạch tại các nút lõi, cũng như không yêu cầu các chuyển mạch ở tốc độ nano giây. Tuy nhiên, cách truyền tải này cũng đặt ra áp lực là làm thế nào để một gói điều khiển BHP kịp lập lịch đặt trước tài nguyên và cấu hình chuyển mạch tại các nút lõi, đảm bảo việc truyền tải chùm quang theo sau; đó chính là nhiệm vụ của hoạt động lập lịch đặt trước tài nguyên tại các nút lõi mạng. Vì vậy vấn đề lập lịch rất cần được quan tâm và nghiên cứu nhằm tối đa hiệu suất băng thông, giảm mất mát dữ liệu và nâng cao hiệu suất hoạt động của mạng OBS. 2. Động lực nghiên cứu Lập lịch là một trong những hoạt động quan trọng trong mạng chuyển mạch chùm quang. Khi gói điều khiển của một chùm đến tại một nút lõi mạng, dựa vào thông tin được chứa trong gói điều khiển như thời điểm đến, thời điểm kết thúc của chùm, lúc này một giải thuật lập lịch sẽ được gọi để tìm kênh bước sóng ra khả dụng để lập lịch cho chùm đến (một kênh bước sóng được gọi khả dụng khi và chỉ khi thời điểm đến của chùm lập lịch lớn hơn LAUT hoặc thời gian đến của chùm nằm trong một khoảng trống (khoảng băng thông nhàn rồi trên một kênh nào đó). Mục đích chính của giải thuật lập lịch là sắp xếp các chùm đến trên các kênh bước sóng ra, nhằm tối đa hiệu suất băng thông sử dụng, giảm số lượng chùm bị loại bỏ và nâng cao hiệu suất hoạt động của mạng OBS. Hiện đã có nhiều giải thuật lập lịch được đề xuất mà có thể được phân vào trong hai nhóm tiếp cận chính: • Phương pháp lập lịch trực tiếp. • Phương pháp lập lịch nhóm. Đối với phương pháp lập lịch trực tiếp khi một gói điều khiển đến một nút 2 lõi mạng, một trong các giải thuật lập lịch trực tiếp [30], [74], [72], [71], [38], [11], [68], [18], [42], [6], [13], [2] sẽ được gọi ngay để tìm kênh bước sóng khả dụng lập lịch cho chùm của nó; nếu có nhiều hơn một kênh bước sóng khả dụng thì giải thuật lập lịch này sẽ chọn một kênh lập lịch mà tối ưu tiêu chí đặt ra của giải thuật. Trong số các giải thuật lập lịch trực tiếp, BF-VF [42] là giải thuật lập lịch tốt nhất về hiệu suất sử dụng băng thông. Tuy nhiên hiệu quả của lập lịch trực tiếp phụ thuộc vào tình trạng băng thông của các kênh ra mà ở đó các chùm đã lập lịch phân bố. Một số giải pháp 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 đã được đề xuất [55], [56], [49], [40], [66], [65], [57], [67], [54], [28], [39]. Cụ thể khi lập lịch trực tiếp không tìm thấy kênh khả dụng, thay vì chùm đến sẽ bị đánh rơi hoàn toàn, lập lịch lại sẽ sắp xếp lại các chùm đã được lập lịch trên các kênh bước sóng nhằm tìm kiếm vị trí băng thông nhàn rỗi để lập lịch cho chùm đến hoặc thực hiện phân đoạn chùm nhằm để chỉ đánh rơi một phần của chùm đến bị tranh chấp. Tuy nhiên lập lịch trực tiếp và lập lịch trực tiếp kết hợp chỉ tối ưu việc lập lịch cho chùm đến hiện thời mà không quan tâm đến các chùm đến sau đó, nên sự phân mãnh băng thông được tạo ra do việc lập lịch chùm hiện thời và có thể ảnh hưởng đến hiệu quả của các lập lịch sau đó. Phương pháp lập lịch nhóm [25], [75], [15], [29], [9], [22], [21], [20] do đó được đề xuất, trong đó các gói điều khiển đến trong một khoảng thời gian sẽ tiến hành lập lịch đồng thời các chùm tương ứng của chúng. Tuỳ thuộc vào các nút lõi mạng có được trang bị bộ chuyển đổi bước sóng đầy đủ hay không, các giải thuật lập lịch nhóm có thể chia thành hai nhóm: Lập lịch nhóm trên đơn kênh trong trường hợp không sử dụng bộ chuyển đổi và lập lịch nhóm trên đa kênh khi được trang bị các bộ chuyển đổi bước sóng đầy đủ. Tuy nhiên các giải thuật lập lịch nêu trên vẫn bộc lộ những tồn tại sau: • Giải thuật lập lịch kết hợp: chưa sử dụng giải thuật lập lịch trực tiếp tối ưu nhất ở giai đoạn 1 để lập lịch cho chùm đến. Việc lập lịch lại của các giải thuật ở giai đoạn 2 chỉ xem xét đối với chùm sau cùng nhất trên các kênh ra. Đoạn chồng lấp khi sử dụng kỹ thuật phân đoạn chùm ở giai đoạn 3 bị loại bỏ. • Giải thuật lập lịch nhóm trên đơn kênh: Độ phức tạp tính toán của các giải thuật cao; chưa tận dụng các khoảng trống băng thông được tạo 3 ra giữa các chùm đã được lập lịch để lập lịch cho các chùm đến và khe thời gian chờ lập lịch được thiết lập với một giá trị cố định mà chưa quan tâm lưu lượng các chùm đến. • Giải thuật lập lịch nhóm trên đa kênh: Các giải thuật theo hướng tiếp cận heuristic chưa đưa ra tiêu chí chọn tối ưu lập lịch cho các chùm đến mà chỉ dựa vào thứ tự sắp xếp. Các giải thuật lập lịch tối ưu làm tăng số lượng gói điều khiển, yêu cầu hệ thống phải có sự thay đổi về mặt giao thức. Hơn nữa việc gỡ hết các chùm đã được lập lịch trên các kênh để đưa về bài toán lập lịch trên máy đồng nhất là không thực tế trên mạng thật. Những tồn tại nêu trên chính là động lực để Luận án tập trung nghiên cứu, cải tiến và đề xuất mới các giải thuật lập lịch nhằm tối thiểu mất mất dữ liệu, tối đa băng thông sử dụng, giảm thời gian chờ lập lịch, giảm độ phức tạp tính toán và nâng cao hiệu quả hoạt động mạng OBS. 3. Mục tiêu nghiên cứu của luận án Mục tiêu của Luận án là nghiên cứu, cải tiến và đề xuất một số giải thuật lập lịch nhằm nâng cao hiệu năng của mạng chuyển mạch chùm quang bao gồm: tối thiểu mất mát dữ liệu, tối đa hiệu suất băng thông, giảm độ trễ và giảm độ phức tạp tính toán. Mục tiêu cụ thể của Luận án là: • Nghiên cứu, cải tiến giải thuật lập lịch trực tiếp kết hợp với lập lịch lại và phân đoạn chùm. • Nghiên cứu, cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đơn kênh. • Nghiên cứu, cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đa kênh. Trên cơ sở mục tiêu nghiên cứu, Luận án được triển khai theo ba vấn đề nghiên cứu chính: • Vấn đề 1 : Cải tiến giải thuật 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. • Vấn đề 2 : Cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đơn kênh. • Vấn đề 3 : Cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đa kênh. 4 4. Đối tượng và phạm vi nghiên cứu • Đối tượng nghiên cứu: Các mô hình, giải thuật lập lịch và các phương pháp xử lý tắc nghẽn trong mạng OBS. • Phạm vi nghiên cứu: Nút lõi mạng OBS. 5. Phương pháp nghiên cứu • Phương pháp nghiên cứu lý thuyết : Tổng hợp các công bố liên quan đến các mô hình, giải thuật lập lịch trong mạng OBS. Phân tích, đánh giá ưu và khuyết điểm của các công trình đã công bố để làm cơ sở cho việc cải tiến hoặc đề xuất mới. Đề xuất các giải thuật lập lịch trực tiếp kết hợp, lập lịch nhóm trên đơn kênh và đa kênh ra nhằm nâng cao hiệu năng mạng, bao gồm: giảm xác suất mất dữ liệu, tăng mức độ sử dụng băng thông, giảm độ trễ đầu cuối và giảm độ phức tạp tính toán. Chứng minh tính đúng đắn và tính toán độ phức tạp của các giải thuật được cải tiến và đề xuất mới. • Phương pháp mô phỏng, thực nghiệm: Cài đặt các giải thuật cải tiến và đề xuất mới nhằm chứng minh hiệu quả của các giải thuật này. Hệ mô phỏng NS2, gói mô phỏng obs-0.9a được sử dụng để tạo dữ liệu mô phỏng và các giải thuật lập lịch được cài đặt bằng ngôn ngữ C++. 6. Nội dung và bố cục của luận án Nội dung của Luận án bao gồm mở đầu, bốn chương nội dung, phần kết luận, danh mục các công trình liên quan đến Luận án và danh mục tài liệu tham khảo. Bốn chương nội dung cụ thể như sau: • Chương 1: "Tổng quan về lập lịch trong mạng chuyển mạch chùm quang" trình bày các kiến thức cơ bản về mạng chuyển mạch chùm quang bao gồm lịch sử phát triển của truyền thông quang, các mô hình chuyển mạch quang, kiến trúc mạng chuyển mạch chùm quang, các hoạt động bên trong mạng và tổng quan về các hướng tiếp cận lập lịch trong mạng chuyển mạch chùm quang. • Chương 2: "Một cải tiến giải thuật lập lịch trực tiếp kết hợp với lập lịch lại và phân đoạn chùm" trình bày tổng hợp các nghiên cứu trước đây về 5 mô hình kết hợp giữa lập lịch trực tiếp, lập lịch lại và phân đoạn chùm. Trên cơ sở các phân tích, so sánh và đánh giá, Luận án đề xuất một cải tiến lập lịch trực tiếp kết hợp với lập lịch lại và phân đoạn chùm nhằm giảm xác suất mất gói tin, giảm số chùm phải lập lịch lại và giảm số chùm bị phân đoạn. • Chương 3: "Một số cải tiến giải thuật lập lịch nhóm trên đơn kênh" trình bày tổng hợp các nghiên cứu liên quan đến lập lịch nhóm trong trường hợp không sử dụng chuyển đổi bước sóng. Trên cơ sở các phân tích, so sánh và đánh giá, Luận án xây dựng mô hình lập lịch nhóm, đề xuất một số giải thuật cải tiến về lập lịch nhóm trên đơn kênh nhằm nâng cao hiệu suất lập lịch bao gồm: giảm xác suất mất mát dữ liệu, giảm độ phức tạp giải thuật và tăng tính thích nghi mô hình lập lịch chuyển biến theo lưu lượng chùm đến. • Chương 4: "Một số cải tiến giải thuật lập lịch nhóm trên đa kênh" trình bày tổng hợp, phân tích, so sánh và đánh giá các nghiên cứu liên quan đến lập lịch nhóm có sử dụng bộ chuyển đổi bước sóng đầy đủ. Từ đó Luận án đề xuất một số giải thuật lập lịch nhóm trên đa kênh theo hai hướng tiếp cận: tối ưu kết quả lập lịch và heuristic nhằm nâng cao hiệu suất lập lịch bao gồm: giảm xác suất mất mát dữ liệu, giảm độ phức tạp giải thuật, giảm độ phức tạp hệ thống và thực tế có thể triển khai trên mạng OBS. 7. Đóng góp của Luận án Các đóng góp chính của Luận án bao gồm: • Đề xuất giải thuật lập lịch trực kết hợp lập lịch lại và phân đoạn chùm iCSA[CT2]. • Đề xuất giải thuật lập lịch nhóm trên đơn kênh LGS[CT8] và các cải tiến LGS-VF[CT4], LAGS[CT5], LAGS-VF[CT7]. • Đề xuất giải thuật lập lịch nhóm trên đa kênh OPT-GS theo hướng tiếp cận tối ưu và LGS-MC[CT6], LGS-MC-VF[CT3], MWC-GS[CT1], MWC- VF-GS[CT1] theo hướng tiếp cận heuristic. 6 Chương 1. TỔNG QUAN VỀ LẬP LỊCH TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG 1.1. Tóm lược lịch sử phát triển của truyền thông quang Trong hơn hai thập kỷ qua, mạng truyền thông đã có một sự tăng trưởng mạnh mẽ. Việc mở rộng nhanh chóng phạm vi bao phủ, cùng với sự bùng nổ các loại hình dịch vụ yêu cầu nhiều băng thông cao như truyền hình Internet (IPTV ), video theo yêu cầu (VoD), điện thoại Internet (VoIP). . . đã làm tăng áp lực nhu cầu băng thông mạng; trong khi khả năng truyền tải của sợi cáp đồng đã đạt đến ngưỡng tới hạn. Điều này đòi hỏi phải phát triển những công nghệ truyền dẫn mới có khả năng đáp ứng những nhu cầu ngày càng cao không chỉ cho hiện tại mà cho cả tương lai. Mạng sợi quang [27], [8], [31] đã được công nhận như một giải pháp tốt nhất có thể đáp ứng những yêu cầu của các dịch vụ băng thông cao nhờ vào những đặc tính có lợi của sợi quang, như độ suy giảm thấp, tiềm năng băng thông rất lớn và khả năng miễn nhiễm đối với nhiễu điện từ. Theo lý thuyết mỗi sợi dẫn quang (hay sợi quang) có thể hỗ trợ băng thông lên đến 50Tb/s [31]. Ngoài ra sợi quang có chi phí sản xuất và độ lỗi bit khá thấp (khoảng 10−2dB). Quá trình phát triển của mạng sợi quang có thể chia thành 3 giai đoạn chính. Thế hệ đầu tiên của mạng sợi quang bao gồm các liên kết WDM điểm-nối-điểm (point-to-point WDM links), mà tại đó tín hiệu quang đến tại một nút được chuyển đổi từ quang sang điện (Optical-to-Electrical), được xử lý trong miền điện và được chuyển đổi ngược lại từ điện sang quang (Electrical-to-Optical) trước khi truyền đến nút...thị vô hướng G được gọi là đầy đủ nếu hai đỉnh bất kỳ của G đều liền kề với nhau. Đồ thị đầy đủ n đỉnh thường được ký hiệu là Kn hoặc Cn. Một clique của đồ thị vô hướng G là một tập con các đỉnh của G sao cho hai đỉnh bất kỳ thuộc nó đều kề nhau. Một tập con các đỉnh của G được gọi là clique cực đại nếu không thể thêm bất kỳ đỉnh nào vào nó để tạo ra clique có số đỉnh lớn hơn. Clique có nhiều đỉnh nhất của G được gọi là clique lớn nhất. Rõ ràng một clique lớn nhất cũng là một clique cực đại, tuy nhiên điều ngược lại không đúng. Một tập con các đỉnh của G sao cho không có hai đỉnh nào thuộc nó là kề nhau được gọi là tập ổn định trong hay tập độc lập của G. Một tập con các đỉnh của G được gọi là tập độc lập cực đại nếu thêm vào bất kỳ một đỉnh nào cũng làm mất tính độc lập của nó, tức là không tồn tại một tập độc lập nào khác chứa nó. Tập độc lập có nhiều phần tử nhất được gọi là tập độc lập lớn nhất. Tập độc lập lớn nhất là tập độc lập cực đại nhưng ngược lại thì không đúng. Số đỉnh của tập độc lập lớn nhất của đồ thị G được gọi là chỉ số độc lập của G. Một đồ thị vô hướng G được gọi là đồ thị khoảng thời gian [10], [16] hay đồ thị khoảng nếu có một phép tương ứng giữa tập các đỉnh V và tập các khoảng thời gian I trên một dòng thời gian, sao cho tồn tại một cạnh giữa hai đỉnh nếu và chỉ nếu hai khoảng thời gian tương ứng có chồng lấp (hoặc không chồng lấp nhau). Đồ thị thời gian tương ứng có chồng lấp được mô tả trong Hình 1.8 và không 24 chồng lấp được mô tả trong Hình 1.9. Hình 1.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 Hình 1.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 Tô màu đồ thị [16], [23] là công cụ hữu dụng trong việc mô hình hóa rất nhiều bài toán khác nhau trong vấn đề xếp lịch, xây dựng chương trình và phân công công việc. Tô màu đồ thị là tô màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau phải có màu khác nhau. Quy hoạch động (Dynamic Programming) là một phương pháp nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu toàn bộ hay một phần kết quả tính toán tại mỗi bước trước đó với mục đích sử dụng lại. Phương pháp quy hoạch động thường được dùng để giải các bài toán tối ưu có bản chất đệ qui, tức là việc tìm phương án tối ưu cho một bài toán quy hoạch động có thể được đưa về việc tìm các phương án tối ưu của một số hữu hạn các bài toán con và quy hoạch động là một trong những phương pháp giảm thời gian thực hiện và độ phức tạp các giải thuật của các bài toán có tính chất trên. 25 1.4.3. Các giải thuật lập lịch đã công bố Lập lịch là một trong những hoạt động quan trọng trong mạng OBS. Khi một gói điều khiển đến tại một nút, tùy thuộc vào đích đến của chùm tương ứng, tài nguyên sẽ dành riêng tại cổng ra, bao gồm kênh bước sóng và khoảng thời gian chiếm giữ sẽ được cấp phát. Đã có nhiều giải thuật lập lịch được đề xuất theo các hướng tiếp cận khác nhau nhằm nâng cao hiệu quả của hoạt động lập lịch. Các giải thuật lập lịch này có thể được phân loại vào: lập lịch trực tiếp [62], [17], [30], [74], [72], [71], [38], [11], [68], [18], [42], [6], [13], [2], lập lịch trực tiếp kết hợp với lập lịch lại và kỹ thuật phân đoạn [55], [56], [49], [40], [66], [65], [57], [67], [54], [28], [40], [5], [39] và lập lịch nhóm [25], [75], [15], [33], [22], [21], [20], [58]. 1.4.3.1. Lập lịch trực tiếp Khi một gói điều khiển đến tại một nút, một giải thuật lập lịch được gọi để lập lịch cho chùm tương ứng trên một kênh dữ liệu ra. Dựa vào thông tin trong gói điều khiển, bộ lập lịch biết được thời điểm đến, độ dài chùm và tiến hành tìm kênh khả dụng để lập lịch cho chùm đó. Hình 1.10: Mô tả các giải thuật lập lịch trực tiếp Các giải thuật lập lịch trực tiếp trong mạng OBS có thể được chia thành 2 26 loại: lập lịch không lấp đầy khoảng trống và lấp đầy khoảng trống [62], [17], [30], [74], [72], [71], [38], [11], [68], [18], [42], [6], [13]. Turner và các cộng sự trong [62], [17] đã đề xuất 2 giải thuật lập lịch không lấp đầy khoảng trống: FFUC (First- Fit Unscheduled Channel) và LAUC (Latest Available Unscheduled Channel). Đối với 2 giải thuật này bộ lập lịch sẽ duy trì các giá trị LAUTi (Latest Available Unscheduled Time) trên mỗi kênh bước sóng ra i; là thời điểm kết thúc của chùm được lập lịch sau cùng nhất, Một kênh sẽ được chọn để lập lịch cho một chùm đến nếu thời điểm đến của chùm lớn hơn giá trị LAUTi. Giải thuật FFUC sẽ chọn kênh khả dụng đầu tiên được tìm thấy để lập lịch cho chùm đến (Hình 1.10a). Giải thuật LAUC sẽ chọn kênh trong số các kênh khả dụng có khoảng trống sinh ra (khoảng gap, khoảng thời gian từ thời điểm đến của chùm ub đến LAUTi) là nhỏ nhất (Hình 1.10b). Lập lịch không lấp đầy khoảng trống có ưu điểm là đơn giản và ít thông tin lưu trữ vì chỉ cần duy trì giá trị LAUT của mỗi kênh. Tuy nhiên nhược điểm của loại lập lịch này là chưa tận dụng được các khoảng trống được tạo ra giữa hai chùm đã được lập lịch trước đó để lập lịch cho chùm mới đến; nên chưa khai thác tốt băng thông của các kênh ra và dẫn đến tỉ lệ rơi chùm cao. Để khắc phục tồn tại này, Xu và cộng sự trong [72], [71] đã đề xuất hai giải thuật lập lịch có lấp đầy khoảng trống (Void-Filling): giải thuật FFUC- VF (First-Fit Unscheduled Channel with Void Filling) và giải thuật LAUC-VF (Latest Available Unscheduled Channel with Void Filling), hay còn có tên gọi khác là Min-SV (Minimal Start Void), là cải tiến từ giải thuật FFUC và LAUC. Đối với loại lập lịch này, bộ lập lịch phải lưu lại thời điểm bắt đầu và kết thúc của các chùm đã lập lịch trên các kênh nhằm khai thác những khoảng trống được tạo ra giữa chúng để lập lịch cho chùm mới đến. FFUC-VF sẽ chọn kênh đầu tiên được tìm thấy có khoảng trống phù hợp (Hình 1.10c), trong khi LAUC-VF chọn trong số các kênh có khoảng trống khả dụng, kênh có khoảng gap được sinh ra ở trước nhỏ nhất để lập lịch cho chùm đến (Hình 1.10d). Một số giải thuật lập lịch lấp đầy khoảng trống khác cũng đã được đề xuất. Lizuka và cộng sự trong [30] cố gắng tối thiểu khoảng gap sinh ra ở sau nhỏ nhất (Hình 1.10e) nên có tên gọi là MinEV (Minimal End Void). Tiêu chí của hai giải thuật BFUC(Best Fit Unscheduled Channel) [42] và BF-VF (Best Fit 27 unscheduled channel with Void Filling) tìm khoảng trống vừa khít nhất để lập lịch cho chùm đến. Trong BF-VF, Nandi và cộng sự định nghĩa một đại lượng về mức độ sử dụng băng thông (utilization) khi lập lịch là: utilization = (burstlenght× 100)/voidlenght Trong đó burstlenght là độ dài chùm và voidlenght là độ dài khoảng trống; BF-VF sẽ chọn kênh với khoảng trống có mức độ sử dụng lớn nhất. Với BFUC, Ljolje và cộng sự sử dụng cách tính khác là chọn kênh có tổng 2 khoảng gap sinh ra trước và sau khi lập lịch chùm đến là nhỏ nhất. Như mô tả ở Hình 1.10f, BF-VF hay BFUC chọn kênh 2 là kênh có khoảng trống vừa khít nhất để lập lịch. 1.4.3.2. Lập lịch trực tiếp kết hợp Các giải thuật lập lịch trực tiếp có thể thất bại khi không tìm thấy kênh khả dụng để lập lịch cho chùm đến. Kết quả là chùm sẽ bị loại bỏ và sẽ gây mất mát dữ liệu lớn, trong khi các chùm đã được lập lịch trên các kênh ra có thể được sắp xếp lại nhằm tạo ra khoảng băng thông rỗi để có thể lập lịch cho chùm đến. Trong trường hợp việc loại bỏ không thể tránh khỏi, kỹ thuật phân đoạn chùm có thể làm giảm mất mát nếu chấp nhận loại bỏ đoạn chồng lấp và phần còn lại của chùm sẽ được lập lịch. Một hướng tiếp cận kết hợp do đó được đề xuất nhằm tránh hay giảm việc loại bỏ toàn bộ chùm. Sau đây là các tiếp cận kết hợp đã được công bố. 1.4.3.2.1. Kết hợp lập lịch trực tiếp và lập lịch lại Ý tưởng của lập lịch lại là sắp xếp lại tài nguyên đối với các chùm đã được lập lịch trên các kênh bước sóng ra, sao cho phần băng thông khả dụng được sinh ra có thể cấp phát cho các chùm đến sau. Mục đích của lập lịch lại là nhằm tăng khả năng sử dụng băng thông trên các kênh ra, giảm mất mát chùm và hạn chế các xử lý phức tạp khác. Tan và cộng sự [57], [56] đề xuất 2 giải thuật lập lịch trực tiếp kết hợp lập lịch lại là ODBR và ABR. ODBR là một giải thuật lập lịch lại đơn mức1 và dựa trên giải thuật lập lịch trực tiếp LAUC. Cụ thể, giải thuật ODBR có hai giai 1Giải thuật chỉ lập lịch lại cho chùm đã được lập lịch sau cùng trên một kênh nào đó 28 đoạn: Giai đoạn 1 gọi giải thuật LAUC để tìm kênh khả dụng lập lịch cho chùm mới đến; Nếu không thể tìm thấy kênh khả dụng, Giai đoạn 2 được gọi để kiểm tra nếu tồn tại một kênh mà trên đó chùm đã được lập lịch sau cùng có thể lập lịch lại sang một kênh khác sao cho khoảng trống được tạo ra là khả dụng cho việc lập lịch chùm mới đến. Khác với ODBR, giải thuật ABR thực hiện lập lịch lại mỗi khi một chùm đến được lập lịch thành công. Giải thuật ABR cũng bao gồm 2 giai đoạn: lập lịch chùm đến với LAUC ở Giai đoạn 1; Nếu lập lịch thành công, Giai đoạn 2 được gọi để lập lịch lại cho các chùm sau cùng trên các kênh khác nếu thỏa mãn điều kiện khoảng trống (void) sau khi di chuyển chùm đến là nhỏ hơn khoảng trống ban đầu. Đây là một giải thuật sắp xếp lại thứ tự các chùm đã lập lịch nhằm giảm tắc nghẽn đối với các chùm đến trong tương lai. 1.4.3.2.2. Kết hợp lập lịch trực tiếp và phân đoạn chùm Ý tưởng phân đoạn chùm được đề xuất đầu tiên bởi Vokkarane và cộng sự trong [65], [66], ở đó chùm được chia thành các đoạn để khi có xung đột xảy ra chỉ có một vài đoạn bị loại bỏ và các đoạn còn lại vẫn được truyền qua mạng. Các đoạn bị mất có thể là phần trước (head dropping) hay phần sau (tail dropping). Vokkarane và cộng sự trong [67] đã đề xuất 2 giải thuật lập lịch kết hợp NP- MOC (Non-Preemptive Minimum Overlapping Channel), NP-MOC-VF (Non- Preemptive Minimum Overlapping Channel Void Filling) có và không lấp đầy khoảng trống. NP-MOC dựa trên giải thuật LAUC. Ngoài các thông tin được sử dụng cho LAUC, NP-MOC duy trì thêm thông tin về khoảng chồng lấp tối thiểu giữa chùm đến với các chùm bị tranh chấp trên tất cả các kênh. Kênh mà với khoảng chồng lấp tối thiểu sẽ được chọn để tối đa phần còn lại của chùm được lập lịch. NP-MOC-VF là tương tự với NP-MOC nhưng có kết hợp với lấp đầy khoảng trống, tức sử dụng giải thuật LAUC-VF. 1.4.3.2.3. Kết hợp lập lịch trực tiếp, lập lịch lại và phân đoạn chùm Không chỉ kết hợp lập lịch trực tiếp với phân đoạn, Umaru, Aydin và cộng sự trong [40], [5] đề xuất một tổ hợp khác giữa lập lịch, lập lịch lại và phân đoạn. Cụ thể, PCSA (Pre-emptive Channel Scheduling Algorithm) trong [40] dựa trên LAUC-VF, ODBR và phân đoạn chùm. Sơ đồ lập lịch kết hợp này được thiết kế nhằm thỏa mãn các yêu cầu QoS trong mạng OBS. Trong [5], một 29 sự kết hợp khác có tên gọi là SODBRA (Segmentation-based On-Demand Burst Rescheduling Algorithm), là tổ hợp của FFUC-VF, ODBR và phân đoạn chùm. Ưu điểm chính của các tổ hợp này nhằm giảm xác suất mất gói khi kết hợp nhiều phương pháp với nhau. Tuy nhiên, giới hạn của chúng đến từ giải thuật lập lịch, lập lịch lại và phân đoạn chùm. Ví dụ SODBRA sử dụng FFUC-VF trong Giai đoạn 1 sẽ không tối ưu khi lấp đầy các khoảng trống, trong khi ODBR trong Giai đoạn 2 chẳng quan tâm đến việc khai thác băng thông của các khoảng trống. PCSA đã cải thiện được vấn đề này bằng cách sử dụng LAUC-VF, nhưng giải thuật này chỉ tối thiểu một bên của khoảng trống. Một tồn tại khác của lập lịch trực tiếp và lập lịch kết hợp là các giải thuật được gọi ngay khi có một gói điều khiển đến nên việc lập lịch tài nguyên cho chùm hiện thời sẽ không quan tâm đến tình trạng của các chùm đến sau nó; Kết quả là băng thông của các kênh dữ liệu ra có thể bị phân mảnh và việc sử dụng băng thông của các kênh ra sẽ không hiệu quả. Ví dụ, xét trường hợp các gói điều khiển (từ b1 đến b8) đến tại một nút mạng OBS trong khe thời gian τ(timeslot) trên một kênh bước sóng ra i như Hình 1.11a. Nếu sử dụng giải thuật lập lịch trực tiếp, chỉ có chùm b1 và b5 được lập lịch (Hình 1.11b), còn các chùm còn lại bị loại bỏ, nhưng nếu các chùm đến này được lập lịch đồng thời thì kết quả lập lịch có thể tốt hơn như Hình 1.11c hay Hình 1.11d. Giải pháp để khắc phục được điểm tồn tại này là lập lịch nhóm. 1.4.3.3. Lập lịch nhóm Trong lập lịch nhóm, một giải thuật lập lịch không được gọi ngay khi một gói điều khiển đến, mà các gói điều khiển đến trong một khe thời gian τ sẽ tiến hành lập lịch đồng thời cho các chùm của chúng. Hình 1.11c và Hình 1.11d mô tả kết quả của lập lịch nhóm dựa trên (c) tối đa tổng số chùm được lập lịch và (d) tối đa tổng độ dài các chùm được lập lịch; Cách làm này rõ ràng tăng hiệu suất băng thông các kênh bước sóng ra. Lập lịch nhóm có thể được chia thành 2 loại: lập lịch nhóm không có chuyển đổi bước sóng, nghĩa là lập lịch nhóm trên đơn kênh và lập lịch nhóm có chuyển đổi bước sóng, nghĩa là lập lịch nhóm trên đa kênh. Hình 1.12 mô tả sự phân loại các giải thuật lập lịch nhóm đã được công bố. 30 Hình 1.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 Giải thuật OBS-GS (OBS Group Scheduling) và MWIS-OS (Maximum Weight Independent Set - Optimal Scheduling) [25], [75], [15] là các ví dụ tiêu biểu của lập lịch nhóm không có chuyển đổi bước sóng, trong đó OBS-GS tìm tất cả các trường hợp lập lịch chùm có thể và chọn trường hợp có tổng số chùm được lập lịch lớn nhất; trong khi MWIS-OS chọn trường hợp có tổng độ dài các chùm được lập lịch lớn nhất. Với trường hợp lập lịch nhóm có hỗ trợ chuyển đổi bước sóng, giả sử các nút OBS được trang bị các bộ chuyển đổi bước sóng đầy đủ, một chùm đến trên một kênh bước sóng có thể được lập lịch trên kênh có bước sóng bất kỳ tại cổng ra. Vì vậy mục tiêu của lập lịch nhóm trên đa kênh là tìm tập các chùm có thể lập lịch với tổng số chùm được lập lịch lớn nhất hoặc tổng độ dài các chùm được lập lịch lớn nhất. Đã có một số đề xuất đối với loại lập lịch nhóm này mà chúng có thể được chia thành 2 nhóm: hướng tiếp cận heuristic bao gồm SSF (Smallest Start-time First), LIF (Largest Interval First), SLV (Smallest-Last Vertex ) và MCF (Maximal Cliques First) [33]; và hướng tiếp cận tối ưu hoá với việc xem xét bài toán lập lịch nhóm trong mạng OBS như bài toán lập lịch công việc trên máy đồng nhất bao gồm GreedyOPT [21] và BATCHOPT [20]. Các phân tích chi tiết về hai hướng tiếp cận này sẽ được trình bày trong Chương 3 và 4. 31 Hình 1.12: Phân loại các giải thuật lập lịch nhóm đã được công bố 1.4.3.4. Kết hợp lập lịch và các giải pháp xử lý tắc nghẽn Việc lập lịch tại một cổng ra có thể thất bại (tắc nghẽn) khi gói điều khiển đến tại một nút lõi yêu cầu lập lịch cho chùm tương ứng của nó trên một kênh (bước sóng) ra, tuy nhiên kênh ra không khả dụng. Giải pháp cho vấn đề này hoặc là làm trễ thời điểm đến của chùm (sử dụng đường trễ FDL) hoặc thay đổi kênh ra (chuyển đổi bước sóng) hoặc lập lịch qua một cổng ra khác (định tuyến lệch hướng). Sau đây là các mô tả về 3 giải pháp xử lý tắc nghẽn này. 1.4.3.4.1. Sử dụng đường trễ FDL Cách tiếp cận sử dụng đường trễ nhằm cố gắng làm trì hoãn thời điểm đến của chùm cho đến khi một kênh bước sóng ra khả dụng để lập lịch cho chùm đó. Trong các mạng chuyển mạch gói điện tử các gói được đệm trong các bộ nhớ truy cập ngẫu nhiên RAM (Random Access Memory) [26], [53] nhưng các bộ đệm quang như RAM hiện không khả dụng; do đó, các đường trễ FDL có thể được sử dụng để làm trễ các chùm ra trong một khoảng thời gian xác định. Phương pháp sử dụng đường trễ làm giảm khả năng chùm bị loại bỏ, nhưng nó không đảm bảo thứ tự đến của các chùm một cách chính xác. Cũng cần chú ý thêm rằng, trong bất kỳ kỹ thuật đường trễ quang nào, kích thước của bộ đệm bị giới hạn rất nghiêm ngặt, không những bởi chất lượng tín hiệu mà còn bởi giới hạn về không gian vật lý. Thực tế, để làm trễ một chùm với thời gian 5ms, chúng ta cần đến hơn 200km sợi quang [31]. 32 1.4.3.4.2. Chuyển đổi bước sóng Với công nghệ WDM, nhiều bước sóng có thể được truyền trên một sợi quang nối giữa hai chuyển mạch quang. Nhiều bước sóng được khai thác nhằm cực tiểu hóa các tranh chấp, ví dụ hai chùm đến yêu cầu lập lịch trên cùng một kênh bước sóng ra tại một cổng ra và cùng thời điểm thì có thể được lập lịch trên hai kênh bước sóng khác nhau như thể hiện trong Hình 1.13. Phương pháp này có thể cực tiểu hóa tranh chấp chùm, khi số lượng các bước sóng trên một sợi quang đơn tiếp tục tăng. Một sợi quang hiện nay có thể mang từ 160 đến 320 bước sóng [19], [32]. Hình 1.13: Mô tả giải pháp chuyển đổi bước sóng w1 qua w2 Chuyển đổi bước sóng là quá trình thay đổi bước sóng của một chùm trên một kênh vào thành một bước sóng khác trên một kênh ra. Việc chuyển đổi bước sóng được thực hiện bởi các bộ chuyển đổi bước sóng. Cách này cho phép tăng khả năng sử dụng lại các bước sóng, tức là cùng một bước sóng có thể được tái sử dụng về mặt không gian để mang các đường quang trên các sợi quang khác nhau trong mạng. Trong mạng OBS có chuyển đổi bước sóng, tranh chấp sẽ được giảm nhờ việc tạo ra nhiều bước sóng khả dụng trên một kết nối. Một chùm tranh chấp có thể được chuyển đến bất kì bước sóng rỗi nào tại cổng ra. Mặc dù chuyển đổi bước sóng đã được chứng minh trong môi trường thí nghiệm, nhưng chưa hoàn toàn khả dụng về mặt thương mại và miền chuyển đổi vẫn bị giới hạn. Do đó có sự phân loại về chuyển đổi bước sóng như sau: • Chuyển đổi hoàn toàn: bất kì một bước sóng vào nào cũng có thể được 33 chuyển đổi thành một bước sóng ra khác. • Chuyển đổi có giới hạn: bước sóng chuyển đổi bị giới hạn vì thế không phải tất cả các kênh vào đều có thể được nối đến các kênh ra. • Chuyển đổi cố định: một kênh vào có thể được nối với một hay nhiều kênh ra đã được xác định trước. • Chuyển đổi có phân bổ thưa thớt: mạng có thể chỉ chứa một số nút có khả năng chuyển đổi hoàn toàn, giới hạn, cố định hay không chuyển đổi bước sóng. 1.4.3.4.3. Định tuyến lệch hướng Định tuyến lệch hướng [45], [60] là một phương pháp giải quyết tắc nghẽn bằng việc định tuyến một chùm tranh chấp đến một cổng ra khác so với cổng ra dự kiến như thể hiện ở Hình 1.14. Trong định tuyến lệch hướng, một chùm được lệch hướng sẽ có đường truyền mới dài hơn, nên làm tăng độ trễ và giảm chất lượng tín hiệu. Hơn nữa, định tuyến lệch hướng có thể tạo ra những đường truyền lặp vô hạn và sẽ gây ra nhiều tắc nghẽn hơn. Vì vậy cần có các cơ chế để ngăn chặn độ dài đường lệch hướng quá mức. Hình 1.14: Mô tả giải pháp định tuyến lệch hướng Một vấn đề khác là chùm lệch hướng cần duy trì thời gian offset thích hợp giữa gói điều khiển và chùm lệch hướng. Khi chùm lệch hướng phải đi qua một hành trình dài hơn so với khi không bị lệch hướng, có thể thời gian offset lúc đầu không còn đủ để gói điều khiển xử lý và cấu hình các chuyển mạch trước khi chùm đến. Để xử lý các trường hợp này, một số chính sách khác nhau có thể được thực hiện, như loại bỏ chùm nếu thời gian offset không đủ hoặc dùng bộ 34 đếm và bộ đo thời gian để phát hiện và giới hạn độ dài hành trình (số hop) mà một chùm đi qua. Cách tiếp cận sử dụng các đường trễ FDL cũng có thể được áp dụng, nhưng nó làm tăng độ phức tạp của lớp quang. 1.4.4. Một số nhận xét các giải thuật lập lịch đã công bố Các giải thuật lập lịch đã được công bố theo các hướng tiếp cận khác nhau nhằm giảm xác suất mất mát dữ liệu, tối ưu hiệu suất băng thông. Tuy nhiêu vẫn còn những tồn tại của các mô hình, giải thuật lập lịch này: • Các giải thuật lập lịch trực tiếp đã đạt đến ngưỡng giới hạn về tối ưu lập lịch cho một chùm đến hiện tại vì vậy cần có các giải thuật lập lịch khác như lập lịch trực tiếp kết hợp với lập lịch lại hay sử dụng kỹ thuật phân đoạn chùm hay lập lịch nhóm, nhằm vượt qua giới hạn này. • Lập lịch nhóm đã được chứng minh là tốt hơn so với lập lịch trực tiếp, dựa trên xác suất mất dữ liệu và hiệu suất khai thác băng thông, nhưng luôn có một sự thỏa hiệp giữa mức độ hiệu quả và độ phức tạp giải thuật. Do đó, cần có những cải tiến sao cho một mặt kết quả lập lịch đạt đến hoặc tiệm cận đến tối ưu, nhưng độ phức tạp giải thuật là chấp nhận được. • Việc lập lịch thực tế phụ thuộc vào trạng thái của chùm đến (như thời điểm đến, độ dài chùm và mức độ ưu tiên nếu xét trong môi trường QoS), phụ thuộc vào tình trạng phân bố băng thông khả dụng trên các kênh ra (tức trạng thái các chùm đã được lập lịch) và phụ thuộc vào các thiết bị hỗ trợ (như bộ chuyển đổi bước sóng, đường trễ FDL. . . ). Do vậy, các giải thuật lập lịch cải tiến phải đạt được trong mối tương quan, hài hòa giữa các yếu tố này. • Việc lập lịch có thể bị thất bại khi chùm đến chồng lấp với tất cả các chùm khác đã được lập lịch trước đó. Phương pháp tiếp cận lập lịch lại có thể tìm thấy khoảng trống cho việc lập lịch một chùm mới đến. Tuy nhiên, trong trường hợp mất mát là không thể tránh khỏi, phân đoạn chùm là một giải pháp hiệu quả nhằm giảm mất mát dữ liệu. Kết hợp lập lịch trực tiếp, lập lịch lại và phân đoạn chùm sẽ nâng cao hiệu quả của lập lịch và giảm mất mát dữ liệu. Vì vậy việc tiếp tục cải tiến, đề xuất mới các mô hình, giải thuật lập lịch 35 là cần thiết nhằm tận dụng băng thông tốt hơn, giảm xác suất mất gói tin và nâng cao hiệu quả hoạt động lập lịch của mạng OBS. 1.5. Tiểu kết Chương 1 Với mục tiêu nghiên cứu về các phương pháp lập lịch trên mạng chuyển mạch chùm quang, chương này của Luận án tập trung nghiên cứu, phân tích và đánh giá các vấn đề liên quan mật thiết đến Luận án. Đầu tiên, Luận án giới thiệu khái quát về mạng chuyển mạch chùm quang cũng như các hoạt động bên trong mạng, qua đó nêu bật lên những ưu điểm của mạng OBS so với các mạng chuyển mạch khác. Sau đó Luận án trình bày các giải thuật lập lịch theo các hướng tiếp cận: lập lịch trực tiếp, lập lịch trực tiếp kết hợp, lập lịch nhóm trên đơn kênh và lập lịch nhóm trên đa kênh đã được công bố. Cuối cùng Luận án đưa ra những đánh giá ưu điểm và những tồn tại và từ đó làm cơ sở để tiếp tục cải tiến, đề xuất mới các giải thuật lập lịch nhằm nâng cao hiệu suất hoạt động của mạng, giảm xác suất mất mát dữ liệu, tối đa băng thông sử dụng, giảm độ trễ và giảm độ phức tạp tính toán. 36 Chương 2. MỘT CẢI TIẾN GIẢI THUẬT LẬP LỊCH TRỰC TIẾP KẾT HỢP VỚI LẬP LỊCH LẠI VÀ PHÂN ĐOẠN CHÙM 2.1. Giới thiệu Các giải thuật lập lịch trực tiếp có thể thất bại trong việc lập lịch một chùm đến nếu băng thông không khả dụng ở các kênh ra. Tuy nhiên, việc lập lịch có thể thực hiện được nếu có một sắp xếp lại đối với các chùm đã được lập lịch trên các kênh ra, sao cho khoảng băng thông nhàn rỗi được tạo ra có thể lập lịch cho chùm đến. Đây chính là ý tưởng của giải thuật ODBR và ABR. Nhưng trong trường hợp loại bỏ chùm là không thể tránh khỏi, phân đoạn chùm là một giải pháp phù hợp nhằm làm giảm mất mát dữ liệu, trong đó chỉ phần chùm chồng lấp là bị loại bỏ, trong khi phần chùm còn lại được lập lịch để truyền đi đến nút kế tiếp. Một kết hợp hoàn chỉnh, bao gồm lập lịch trực tiếp, lập lịch lại và phân đoạn chùm như PCSA và SODBRA đã được đề xuất nhằm lập lịch hiệu quả hơn đối với chùm đến. Nội dung trong chương này sẽ trình bày và phân tích chi tiết các giải thuật lập lịch trực tiếp kết hợp lập lịch lại và phân đoạn chùm đã được công bố. Trên cơ sở đánh giá và chỉ ra các điểm tồn tại của các giải thuật này, một cải tiến lập lịch kết hợp được chúng tôi đề xuất nhằm nâng cao hiệu suất băng thông và làm giảm xác suất mất dữ liệu. 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ố Các giải thuật lập lịch kết hợp có thể được phân loại như sau: • Lập lịch trực tiếp kết hợp với lập lịch lại gồm ODBR và ABR [57], [56]. • Lập lịch trực tiếp kết hợp với phân đoạn chùm gồm NP-MOC, NP-MOC- 37 VF[65], [67]. • Lập lịch trực tiếp kết hợp với lập lịch lại và phân đoạn chùm gồm PCSA và SODBRA [40], [5]. 2.2.1. Giải thuật ODBR ODBR(On-Demand Burst Rescheduling) là một giải thuật lập lịch lại đơn mức và dựa trên giải thuật lập lịch trực tiếp LAUC. Giải thuật ODBR thực hiện 2 giai đoạn: • Giai đoạn 1: gọi giải thuật LAUC tìm kênh khả dụng để lập lịch cho chùm đến. Nếu việc lập lịch không thành công, Giai đoạn 2 sẽ được gọi. • Giai đoạn 2: thực hiện lập lịch lại đối với một chùm sau cùng đã được lập lịch trên một kênh ra nào đó sao cho khoảng băng thông nhàn rỗi được tạo là khả dụng để lập lịch cho chùm đến. Ví dụ trong Hình 2.1a mô tả tình trạng các chùm đã được lập lịch trên 2 kênh ra w1, w2. Khi có một chùm ub đến, ODBR gọi giải thuật LAUC để tìm kênh khả dụng cho việc lập lịch chùm ub. Nếu không tìm thấy kênh khả dụng, ODBR thực hiện lập lịch lại một trong các chùm đã được lập lịch sau cùng nhất trên 2 kênh ra w1, w2. Trong ví dụ này, chùm b3 trên kênh w1 sẽ được lập lịch lại trên kênh w2 (xem Hình 2.1b) và tạo ra khoảng trống khả dụng trên kênh w1 để lập lịch cho chùm đến ub. Hình 2.1: Một ví dụ về lập lịch lại của giải thuật ODBR 38 Ưu điểm: Giải thuật ODBR tăng khả năng lập lịch nhờ vào việc lập lịch lại một trong các chùm đã được lập lịch nên giảm được xác suất mất chùm và tăng hiệu suất băng thông của các kênh ra. Tồn tại: Giải thuật ODBR sử dụng giải thuật LAUC ở Giai đoạn 1 nên chưa tận dụng khoảng trống được tạo ra giữa các chùm đã được lập lịch trước đó để lập lịch cho chùm đến. Như ví dụ ở Hình 2.1, nếu sử dụng giải thuật lập lịch có lấp đầy khoảng trống thì chùm đến ub sẽ được lập lịch trên kênh w1, mà không cần phải lập lịch lại cho chùm b3. Hơn nữa ODBR chỉ lập lịch lại đối với các chùm đã được lập lịch sau cùng trên các kênh, nên nếu chùm ub chồng lấp với chùm đã lập lịch không phải chùm cuối cùng thì ODBR thất bại. 2.2.2. Giải thuật ABR Giải thuật ABR(Aggressive Burst Rescheduling) thực hiện lập lịch lại mỗi khi một chùm đến được lập lịch thành công. Tương tự ODBR, ABR cũng bao gồm 2 giai đoạn: • Giai đoạn 1: gọi giải thuật LAUC tìm kênh khả dụng để lập lịch cho chùm đến. Nếu việc lập lịch thành công, Giai đoạn 2 của giải thuật ABR sẽ được gọi. • Giai đoạn 2: thực hiện lập lịch lại cho các chùm đã được lập lịch sau cùng trên các kênh ra sao cho khoảng trống giữa các chùm đã được lập lịch nhỏ hơn khoảng trống ban đầu. Giai đoạn 2 của giải thuật ABR thực chất là công việc sắp xếp lại thứ tự các chùm sau cùng nhằm chuẩn bị sẵn băng thông rỗi cho việc lập lịch các chùm đến tiếp theo. Ví dụ trong Hình 2.2a mô tả trường hợp khi chùm b4 đến được lập lịch thành công lên kênh w2 (Giai đoạn 1), chùm sau cùng (chùm b3) trên kênh w1 tiếp tục được lập lịch lại (Giai đoạn 2) sang kênh w2 vì khoảng trống được tạo ra sẽ nhỏ hơn (Hình 2.2b). Ở Hình 2.2c chùm b5 đến sau đó được lập lịch lên kênh w2 (Giai đoạn 1). Cuối cùng, chùm b6 đến tiếp đó được lập lịch lên w1 (Giai đoạn 1), chùm sau cùng (chùm b5) trên kênh w2 sẽ được lập lịch lại (Giai đoạn 2) sang kênh w1 vì khoảng trống sau khi lập lịch lại là nhỏ hơn (Hình 2.2e). Ưu điểm: Giải thuật ABR là làm tăng khả năng lập lịch đối với các chùm 39 Hình 2.2: Một ví dụ cơ chế hoạt động của giải thuật lập lịch lại ABR đến sau, vì vậy tăng hiệu suất băng thông của các kênh ra. Tồn tại: Tương tự như giải thuật ODBR, do sử dụng giải thuật LAUC để lập lịch cho các chùm đến ở Giai đoạn 1 nên giải thuật ABR chưa tận dụng hết khoảng trống được tạo ra giữa hai chùm đã được lập lịch trước đó. Bên cạnh đó giải thuật ABR lập lịch lại liên tục khi một chùm đến được lập lịch thành công nên làm tăng số lượng gói điều khiển phải gửi lại vì vậy tăng độ phức tạp của hệ thống. 2.2.3. Kỹ thuật phân đoạn chùm Ý tưởng phân đoạn chùm được đề xuất đầu tiên bởi Vokkarane và cộng sự[65], [66], trong đó một chùm được chia thành các đoạn (Hình 2.3), mỗi đoạn bao gồm phần tiêu đề(header) và phần dữ liệu(payload). Phần tiêu đề chứa thông tin về bit đồng bộ(Guard Bits), kiểu dữ liệu(Payload Type), định danh đoạn(Seg Id), độ dài đoạn(Segment leght) và thông tin sửa lỗi(Checksum). Mỗi đoạn có thể mang bất kỳ loại dữ liệu nào, như các gói IP hoặc tế bào ATM (Hình 2.3). 40 Hình 2.3: Phân đoạn chùm và cấu trúc bên trong của header của đoạn Khi chùm đến chồng lấp với môt chùm đã được lập lịch trên một kênh ra (Hình 2.4), chỉ đoạn chồng lấp mới bị loại bỏ thay vì loại bỏ toàn bộ chùm. Hình 2.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 Một vấn đề trong phân đoạn chùm là lựa chọn phương án loại bỏ các đoạn chồng lấp. Có hai cách tiếp cận, gồm: • Loại bỏ phần đầu, trong đó các đoạn đầu của chùm đến(chùm tranh chấp) bị loại bỏ (Hình 2.4a). • Loại bỏ phần đuôi, trong đó các đoạn đuôi của chùm đến(chùm tranh chấp) bị loại bỏ (Hình 2.4b). Ưu điểm của loại bỏ phần đuôi so với loại bỏ phần đầu của phân đoạn chùm 41 là không làm thay đổi trật tự các gói tin đến tại đích, với giả định rằng các gói tin được truyền lại sau một thời gian. Để tăng hiệu quả của lập lịch trực tiếp kết hợp, một kết hợp cả lập lịch trực tiếp, lập lịch lại và phân đoạn chùm đã được đề xuất trong [40], [5] và sẽ được mô tả trong 2 mục tiếp theo. 2.2.4. Giải thuật SODBRA Giải thuật SODBRA(Segmentation-based On-Demand Burst Rescheduling Algorithm)[5] là kết hợp giữa giải thuật lập lịch trực tiếp FFUC-VF, ODBR và kỹ thuật phân đoạn chùm. Trình tự thực hiện của giải thuật SODBRA bao gồm 3 giai đoạn: Giai đoạn 1: gọi giải thuật FFUC-VF tìm kênh đầu tiên có khoảng trống khả dụng để lập lịch cho chùm đến. Nếu việc lập lịch không thành công, Giai đoạn 2 sẽ được gọi. Giai đoạn 2: gọi giải thuật lập lịch lại ODBR được gọi để sắp xếp lại chùm đã được lập lịch sau cùng trên các kênh sao cho có thể tạo ra được khoảng trống mà có thể lập lịch được cho chùm đến (lưu ý rằng OBDR chỉ thực hiện di chuyển đơn mức, có nghĩa là chỉ có chùm sau cùng của các kênh ra mới được di chuyển và không xem xét lấp đầy khoảng trống trong khi lập lịch). Trong trường hợp không thể lập lịch lại được, Giai đoạn 3 của giải thuật sẽ được gọi. Giai đoạn 3: phân đoạn chùm được gọi để loại bỏ đoạn ch...v) := 0; 92 6 foreach (u, v) ∈ E và L(u,v) 6= true do 7 C(u,v) := {u, v}; 8 W(u,v) := lu + lv; 9 VCad := adj(u) ∩ adj(v); VCad là tập các đỉnh ứng cử viên 10 while (VCad 6= ∅) do 11 C(u,v) := C(u,v) ∪ {u′} với u′ ∈ VCad; 12 W(u,v) := W(u,v) + l(u′); 13 VCad := VCad r {u′}; 14 Loại bỏ tất cả u1 ∈ VCad ra khỏi tập VCad nếu (u′, u1) ∈ E; 15 if (|C(u,v)| = n) then 16 Cmax := C(u,v); 17 return Cmax; 18 else 19 if (W(u,v) > Wmax) then 20 Wmax := W(u,v); Cmax := C(u,v); 21 foreach v ∈ V do 22 if (adj(v) = ∅) then 23 Cv := v; Wv := lv; 24 if (Wv > Wmax)) then 25 Wmax := Wv; Cmax := Cv; 26 return Cmax; Từ các nhận xét trên có thể kiểm chứng được hàm findMWC tìm ra được Cmax là một clique cực đại và có tổng trọng số các đỉnh là lớn nhất. Độ phức tạp của findMWC được xác định như sau: Dòng 1 đến dòng 2: Tìm tập các đỉnh lân cận với một đỉnh bất kỳ nào đó có độ phức tạp là O(|V |). Dòng 3 đến dòng 5: Khởi tạo các nhãn L(u,v) có độ phức tạp là O(|E|). Dòng 6 đến dòng 20: Tìm đồ thị con đầy đủ xuất phát từ một cạnh (u, v) có độ phức tạp O(|E| × |V | × log |V |). 93 Dòng 21 đến dòng 25: Tìm đồ thị con đầy đủ với các đỉnh cô lập có độ phức tạp O(|V |). Độ phức tạp của hàm findMWC tìm clique cực đại Cmax có trọng số lớn nhất là O(|E| × |V | × log |V |). 4.3.3.3. Lập lịch các chùm từ clique cực đại Cmax Do các đỉnh (bki ) của clique cực đại Cmax chứa đầy đủ thông tin về chùm nào được lập lịch trên kênh nào nên giải thuật lập lịch các chùm từ clique cực đại chỉ đơn giản phân phối mỗi chùm bi lên kênh k tương ứng. Hàm ScheduleBurstsfromMWC được mô tả như sau: Function scheduleBurstsfromMWC Input : Cmax; Output: I ′; 1 foreach bki ∈ Cmax do 2 Lập lịch chùm bi trên kênh thứ k; 3 I ′ := I ′ ∪ {bi}; 4 return I ′; Hàm ScheduleBurstsfromMWC lập lịch các chùm từ clique cực đại có độ phức tạp là O(|V |). 4.3.3.4. Độ phức tạp của giải thuật MWC-GS Độ phức tạp của giải thuật MWC-GS được xác định như sau: Bước 1: Xây dựng đồ thị khoảng có độ phức tạp O(n2). Bước 2: Tìm clique cực đại có tổng trọng số lớn nhất có độ phức tạp O(|E| × |V | × log |V |). Bước 3: Lập lịch cho các chùm tương ứng các đỉnh trong Cmax có độ phức tạp O(|V |). Bước 1 đến bước 3 thực hiện độc lập vì vậy độ phức tạp của giải thuật MWC-GS là O(|E| × |V | × log |V |). 94 4.3.3.5. Mở rộng giải thuật MWC-GS với lấp đầy khoảng trống Giải thuật MWC-GS được mô tả ở trên chỉ xem xét đối với trường hợp không lấp đầy khoảng trống, tức là điều kiện để lập lịch đối với một chùm đến bi trên một kênh k là thời điểm đến của bi sau LAUT của kênh k. Tuy nhiên, trong trường hợp có lấp đầy khoảng trống, phần băng thông nhàn rỗi được sinh ra giữa các chùm đã được lập lịch trước đó sẽ được xem xét để sử dụng. Cải tiến của MWC-GS với lấp đầy khoảng trống chỉ đơn giản được thực hiện trong khi xây dựng đồ thị khoảng (hàm constructGraph). Các hàm còn lại, findMWC và scheduleBurstsfromMWC không có thay đổi nào. Hình 4.14: (a)Ví dụ về các chùm đến và (b) kết quả lập lịch tối ưu có lấp đầy khoảng trống trên 2 kênh Hình 4.15: (a) Đồ thị khoảng biểu diễn các khả năng lập lịch có lấp đầy khoảng trống của các chùm đến trong Hình 4.14a và (b) Clique được tìm thấy tương ứng với kết quả lập lịch trong Hình 4.14b 95 Trong giải thuật MWC-GS có lấp đầy khoảng trống (with Void Filling), được gọi là MWC-VF-GS, một chùm đến sẽ được so sánh với với khoảng trống trên mỗi kênh. Như được mô tả trong Hình 4.14, nếu điều kiện si > ekj và (si + li) < s k (j+1) được thỏa mãn thì kênh k được chọn cho việc lập lịch chùm bi. Đồ thị khoảng biểu diễn khả năng lập lịch khi đó có dạng như Hình 4.15. Tóm lại, với trường hợp có lấp đầy khoảng trống, điều kiện ở dòng 3 của hàm constructGraph được sửa thành: (si > ekj ) ∧ ((si + li) < sk(j+1)). 4.4. Mô phỏng và phân tích kết quả Luận án thực hiện cài đặt các mô hình lập lịch nhóm đã đề xuất LGS-MC, MWC-GS, MWC-VF-GS, OPT-GS và so sánh dựa trên xác suất mất gói tin và thời gian thực hiện với các giải thuật đã được đề xuất trước đó trong môi trường mô phỏng được trình bày ở mục 2.4. Các tham số mô phỏng: τ được thiết lập 700µs. Mô phỏng được thực hiện từ tải lưu lượng 0.1 đến 0.9. Luận án sử dụng 2 mô hình mạng mô phỏng: một là mạng Dumbbell (Hình 3.10 ở Mục 3.4) và mạng NSFNET (Hình 2.7 ở Mục 2.4). Các mục đích mô phỏng bao gồm: • So sánh xác suất mất gói tin của các giải thuật lập lịch nhóm trên đa kênh đã công bố với giải thuật lập lịch đề xuất theo hai hướng tiếp cận: heuristic và tối ưu kết quả lập lịch. • Đánh giá sự ảnh hưởng của khe thời gian τ đến hiệu quả lập lịch của các giải thuật lập lịch nhóm trên đa kênh. Hình 4.16 và Hình 4.17 với so sánh xác suất mất gói tin của 4 giải thuật heuristic SLV, MCF, SSF, LIF được công bố và hai giải thuật đề xuất LGS-MC, MWC-GS. Trong đó giải thuật LGS-MC, MWC-GS có xác suất mất gói tin thấp hơn so với 4 giải thuật còn lại. Điều này cho thấy giải thuật LGS-MC và MWC-GS với điều kiện chọn lập lịch tối ưu trên mỗi kênh và nhiều kênh nên đạt kết quả tốt hơn, trong đó giải thuật MWC-GS có xác suất mất gói thấp nhất. Bên cạnh đó xác suất mất gói tin của 4 giải thuật SLV, MCF, SSF, LIF trên 2 mô hình mạng cho các kết quả khác nhau, trong mô hình Dumbbell giải thuật LIF cho kết quả tốt nhất, tuy nhiên trong mô hình mạng NSFNET-14 nút thì 96 giải thuật SSF là tốt nhất, điều nay có thể giải thích đó là do các cách sắp xếp các chùm theo các tiêu chí của mỗi giải thuật vì vậy trong mỗi trường hợp tuỳ thuộc vào tình trạng các chùm đến thì mỗi giải thuật có kết quả xác suất mất gói tin khác nhau. Hình 4.16: So sánh xác suất mất gói tin của LGS-MC, MWC-GS với các giải thuật heuristic trên mô hình mạng Dumbbell Hình 4.17: So sánh xác suất mất gói tin của LGS-MC, MWC-GS với các giải thuật heuristic trên mô hình mạng NSFNET-14 nút Kết quả mô phỏng thể hiện ở Hình 4.18 và Hình 4.19 cho thấy giải thuật đề xuất LGS-MC, MWC-GS cho kết quả xác xuất mất gói tin thấp hơn so với giải thuật GreedyOPT, bởi vì đối với giải thuật GreedyOPT dựa trên ý tưởng của giải thuật tham lam khi sắp xếp các chùm theo thời điểm đến sớm nhất và thực 97 hiện lập lịch cho các chùm trong danh sách đó, với cách làm này GreedyOPT chỉ tối ưu trong trường hợp các chùm có độ dài bằng nhau, tuy nhiên khi độ dài chùm biến thiên thì việc lập lịch của GreedyOPT không hiệu quả. Hình 4.18: So sánh xác suất mất gói tin của LGS-MC, MWC-GS với GreedyOPT trên mô hình mạng Dumbbell Hình 4.19: So sánh xác suất mất gói tin của LGS-MC, MWC-GS với GreedyOPT trên mô hình mạng NSFNET-14 nút Mặc khác, GreedyOPT gỡ các chùm đã được lập lịch ra và thực hiện lập lịch lại với các chùm đến, tuy nhiên không đảm bảo rằng các chùm này sẽ được lập lịch lại qua một kênh khác hay phải loại bỏ, điều này sẽ dẫn đến tăng số lượng gói điều khiển gửi lại và do đó cũng làm tăng xác suất tắc nghẽn trong mạng. Một chứng minh bằng thực nghiệm về tỉ lệ các chùm đã được lập lịch, bị gỡ ra và không thể lập lịch lại được trình bày chi tiết ở bảng 4.1. Qua đó cho thấy tỷ 98 lệ lập lịch lại thành công của các chùm đã lập lịch trước đó bị gỡ ra chi đạt 86%. Vì vậy số gói điều khiển trong mạng sẽ tăng lên khoảng 24%. Bảng 4.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 Tải Số chùm bị loại bỏ Số chùm lập lịch lại Tỉ lệ lập lịch lại qua kênh khác thành công (%) 0.1 319 276 86.52 0.2 392 327 83.42 0.3 560 481 85.89 0.4 620 537 86.61 0.5 739 646 87.42 0.6 797 692 86.83 0.7 929 803 86.44 0.8 1072 805 75.09 0.9 1286 905 70.30 Kết quả mô phỏng ở Hình 4.20 và Hình 4.21 so sánh xác suất mất gói tin của giải thuật lập lịch tối ưu đề xuất OPT-GS và MWC-VF-GS (một cải tiến của giải thuật MWC-GS) với giải thuật BATCHOPT chỉ ra rằng MWC-VF-GS có xác suất mất gói tiệm cận với BATCHOPT, trong khi hiệu quả của OPT-GS gần tương đương với BATCHOPT. Điều này được giải thích rằng với giải thuật BATCHOPT thực hiện gỡ các chùm đã được lập lịch trước đó và thực hiện lập lịch lại cùng với các chùm đến hiện tại. Để tìm được tập các chùm tối ưu có tổng trọng số lớn nhất để lập lịch trên đa kênh ra giải thuật BATCHOPT thực hiện xây dựng đồ thị luồng và tìm luồng cực tiểu trên đồ thị đó và loại bỏ, việc làm này sẽ dẫn đến tập các chùm còn lại trên đồ thị chính là tập các chùm lập lịch trên đa kênh ra tối ưu vì vậy kết quả lập lịch của giải thuật BATCHOPT là tối ưu lập lịch toàn cục. Đối với giải thuật OPT-GS và MWC-VF-GS chỉ tối ưu với tập các chùm đến lập lịch hiện tại. Tuy nhiên giải thuật BATCHOPT cũng giống như GreedyOPT các chùm đã được lập lịch trước đó sẽ gỡ ra vì vậy nó làm gia tăng số gói điều khiển, thay đổi lại giao thức truyền và không thực tế để ứng dụng trong mạng OBS như ví dụ ở Hình 4.8. 99 Hình 4.20: So sánh xác suất mất gói tin của MWC-VF-GS, OPT-GS với BATCHOPT trên mô hình mạng Dumbbell Hình 4.21: So sánh xác suất mất gói tin của MWC-VF-GS, OPT-GS với BATCHOPT trên mô hình mạng NSFNET-14 nút Kết quả trong Hình 4.22 mô tả ảnh hưởng của kích thước khe thời gian τ đến hiệu quả lập lịch nhóm của các giải thuật cho thấy khi tăng kích thước khe thời gian τ thì xác suất mất gói tin giảm, đây cũng là một ưu điểm của lập lịch nhóm và điều này cũng giải thích vì sao giải thuật BATCHOPT tốt hơn giải thuật OPT-GS. Tuy nhiên kích thước τ còn phụ thuộc và yếu tố độ trễ và thời gian sống của các gói tin vì vậy kích thước khe thời gian τ được thiết lập để thỏa mãn các ràng buộc trên. 100 Hình 4.22: So sánh ảnh hưởng của kích thước khe thời gian τ đến hiệu quả lập lịch nhóm của MWC-VF-GS, OPT-GS với BATCHOPT 4.5. Tiểu kết Chương 4 Chương này của Luận án đã trình bày, phân tích và đánh giá chi tiết các giải thuật lập lịch nhóm trên đa kênh ra đã được công bố của các tác giả theo hai hướng tiếp cận tối ưu lập lịch và heuristic, từ đó đưa ra được những ưu điểm và tồn tại của các giải thuật này. Để khắc phục những tồn tại của các giải thuật trên nhằm cải thiện tốt hoạt động lập lịch, giảm xác suất mất mát dữ liệu và nâng cao hiệu năng băng thông, Luận án đã xây dựng bài toán lập lịch và đề xuất 3 giải thuật lập lịch nhóm LGS-MC, MWC-GS và OPT-GS dựa trên hai hướng tiếp cận heuristic và tối ưu lập lịch. Trong đó giải thuật MWC-GS và OPT-GS mô hình hoá bài toán lập lịch nhóm trên đa kênh qua bài toán tìm clique cực đại và tìm đường đi trên đơn đồ thị khoảng vô hướng có trọng số và đơn đồ thị có hướng có trọng số. Qua kết quả mô phỏng cho thấy các giải thuật lập lịch đề xuất và các cải tiến của nó cho kết quả tốt hơn so với các giải thuật lập lịch nhóm đã được công bố theo hướng tiếp cần heuristic thông qua xác suất mất gói tin giảm, độ phức tạp giải thuật nhỏ hơn. Đối với giải thuật OPT-GS theo hướng tiếp cận tối ưu không làm gia tăng số lượng gói điều khiển, thay đổi giao thức truyền thông hiện tại và thực tế có thể triển khai trên mạng thật. 101 KẾT LUẬN Kết luận Chuyển mạch chùm quang (OBS) trên mạng WDM được xem là một công nghệ đầy triển vọng đối với mạng Internet thế hệ tiếp theo, bởi vì mạng OBS khắc phục được những hạn chế về công nghệ của chuyển mạch gói quang hiện tại và khai thác băng thông linh hoạt, tốt hơn hơn chuyển mạch kênh quang. Tuy nhiên như các loại mạng chuyển mạch gói khác, tắc nghẽn có thể xảy ra khi một gói điều khiển đến yêu cầu lập lịch cho chùm của nó nhưng không tìm kênh khả dụng; trong trường hợp này chùm đến sẽ bị đánh rơi. Vì vậy vấn đề lập lịch trong mạng OBS rất quan trọng trong việc giảm mất mát dữ liệu và tăng hiệu suất của mạng. Với mục đích đó Luận án đã tập trung nghiên cứu các mô hình, giải thuật lập lịch trong mạng OBS với các hướng tiếp cận khác nhau. Kết quả mà Luận án đã đạt được bao gồm: 1) Tổng hợp phân tích, đánh giá và phân lớp các giải thuật lập lịch đã được công bố theo các hướng tiếp cận khác nhau trong mạng OBS. Qua đó đưa ra được những ưu điểm và tồn tại của các giải thuật và đây chính là cơ sở để đề xuất và cải tiến các giải thuật lập lịch nhằm tối thiểu mất mát dữ liệu, tối đa hiệu suất băng thông, giảm độ trễ và giảm độ phức tạp tính toán. 2) Đề xuất giải thuật lập lịch iCSA kết hợp giữa lập lịch trực tiếp, cải tiến lập lịch lại và kỹ thuật phân đoạn chùm. Kết quả cài đặt mô phỏng đã chứng minh giải thuật lập lịch đề xuất iCSA có xác suất mất gói tin thấp hơn và giảm số lượng chùm bị phân đoạn so với các giải thuật đã được công bố trước đó[CT2]. 3) Đề xuất giải thuật lập lịch nhóm trên đơn kênh LGS và các giải thuật lập lịch cải tiến LGS-VF và LAGS-VF có độ phức tạp thấp hơn so với các giải thuật lập lịch nhóm đã được công bố trước đó. Kết quả cài đặt mô phỏng đã chỉ ra rằng giải thuật lập lịch nhóm đề xuất có xác suất mất gói tin thấp hơn các giải thuật lập lịch cùng loại. Bên cạnh đó, giải thuật LAGS 102 và LAGS-VF còn cải thiện đáng kể độ trễ nên mang lại hiệu quả lâu dài đối với các hoạt động lập lịch tại các nút khác và các hoạt động truyền thông khác trong mạng[CT4], [CT5], [CT7], [CT8]. 4) Đề xuất giải thuật lập lịch nhóm trên đa kênh LGS-MC, MWC-GS, MWC- VF-GS theo hướng tiếp cận heuristic và lập lịch nhóm theo hướng tiếp cận tối ưu OPT-GS. Qua kết quả mô phỏng cho thấy các giải thuật để xuất có xác suất mất gói tin thấp hơn so với các giải thuật cùng loại. Bên cạnh đó trong hai giải thuật MWC-GS và OPT-GS, Luận án đưa ra một cách tiếp cận trên đồ thị để giải quyết bài toán lập lịch nhóm trên đa kênh trong mạng OBS, hơn nữa giải thuật đề xuất GS-OPT theo hướng tiếp cận tối ưu không làm gia tăng số lượng gói điều khiển, không thay đổi giao thức truyền thông hiện tại và thực tế có thể triển khai trên mạng thật.[CT1], [CT3], [CT4], [CT6]. Những vấn đề cần tiếp tục nghiên cứu Từ những kết quả đạt được trong Luận án các vấn đề cần được quan tâm nghiên cứu trong thời gian tới: • Ứng dụng logic mờ trong điều khiển khe thời gian lập lịch nhằm có sự co giản mịn hơn. • Xây dựng các giải thuật lập lịch nhằm đáp ứng vấn đề chất lượng dịch vụ cho mạng OBS. 103 DANH MỤC CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN LUẬN ÁN CT1. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. Near-Optimal Algorithm for Group Scheduling in OBS Networks. ETRI Journal (SCIE), 2015, Vol: 37, No: 5, pp: 888-897. CT2. Vo Viet Minh Nhat, Nguyen Hong Quoc. An Improved Composite Scheduling Approach for Reducing Data Loss in OBS Networks. Proceeding of SoICT 2015 (ACM ICPS, ISBN:978-1-4503-3843-1), pp: 143-148. CT3. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. A Group Scheduling Algorithm with Void Filling for Multi-Channel in OBS Networks. Journal of Science, Hue University, Vol. 107, No. 08, 2015, pp. 77-87, 2015. (ISSN: 1859-1388) CT4. Nguyen Hong Quoc, Vo Viet Minh Nhat, Nguyen Hoang Son. An Algorithm of Group Scheduling with Void Filling in OBS Core Nodes. Advanced in Computer Science and its Applications, Lecture Notes in Electrical Engineering, 2014, No: 279, pp: 107-114. CT5. Vo Viet Minh Nhat, Nguyen Hong Quoc. A Model of Adaptive Grouping Scheduling in OBS Core Nodes. Journal of Convergence, 2014, Vol: 5, No: 1, pp: 9-13. CT6. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. Group Scheduling for MultiChannel in OBS Networks. REV Journal on Electronics and Communications, 2014, Vol: 3, No: 3–4, pp: 134-137. CT7. Vo Viet Minh Nhat, Nguyen Hong Quoc, Nguyen Hoang Son. A New Algorithm of Group Scheduling in OBS Core Nodes. Proceedings of IEEE 2013 International Con- ference on Advanced Technologies for Communications (ATC2013), 2013, pp: 592-596. CT8. Nguyễn Hồng Quốc, Võ Viết Minh Nhật, Nguyễn Hoàng Sơn. Một mô hình lập lịch nhóm trên mạng chuyển mạch chùm quang. Hội nghị Khoa học Quốc gia lần thứ VI về nghiên cứu cơ bản và ứng dụng Công nghệ thông tin(FAIR), 2013. 104 TÀI LIỆU THAM KHẢO [1] N. Akar, C. Raffaelli, M. Savi, and E. Karasan. Shared-per-wavelength asynchronous optical packet switching: A comparative analysis. Computer Networks, 54(13):2166–2181, 2010. [2] S. Al Omar, A. Mesleh, and A. Al-Qaisi. Binary heap based fair scheduling algorithm in optical burst switching networks. International Review on Computers and Software (IRECOS), 11(3):224–231, 2016. [3] K. Aparna, S. Venkatachalam, and G. Babu. Wdm optical network. Wireless Commu- nication, 2(5):120–125, 2010. [4] E. M. Arkin and E. B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18(1):1–8, 1987. [5] M. A. Aydin, T. Atmaca, O. Turna, and H. Zaim. Performance study of new obs channel scheduling algorithms in a multiservice network. In Networking and Services, 2009. ICNS’09. Fifth International Conference on, pages 242–248. IEEE, 2009. [6] M. A. Aydin, T. Atmaca, O. C. Turna, and H. Zaim. Performance study of new OBS channel scheduling algorithms in a multiservice network. In Proceedings of the 5th In- ternational Conference on Networking and Services, ICNS 2009, pages 242–248, 2009. [7] S. Azodolmolky, A. Tzanakaki, and I. Tomkos. A simulation study of adaptive burst assembly algorithms in optical burst switched networks with self-similar traffic sources. Annales des Telecommunications/Annals of Telecommunications, 62(5-6):584–603, 2007. [8] T. Battestilli and H. Perros. An introduction to optical burst switching. Communications Magazine, IEEE, 41(8):S10–S15, 2003. [9] X. Cao, J. Joseph, J. Li, and C. Xin. Serialised batch scheduling algorithm for optical burst switching networks. The Institution of Engineering and Technology, 3(August 2007):353– 362, 2009. [10] M. C. Carlisle and E. L. Lloyd. On the k-coloring of intervals. Discrete Applied Mathe- matics, 59(3):225–235, 1995. [11] M. Casoni, E. Luppi, and M. L. Merani. Performance evaluation of channel schedul- ing algorithms with different QOS classes. In Proceedings - 2006 IEEE International 105 Conference on Networks, ICON 2006 - Networking-Challenges and Frontiers, volume 2, pages 280–285, 2006. [12] P. K. Chandra, A. K. Turuk, and B. Sahoo. Survey on optical burst switching in WDM networks. In 2009 International Conference on Industrial and Information Systems (ICIIS), pages 83–88, 2009. [13] D. Chandran and J. Stephen. A novel scheduling algorithm in OBS networks. Journal of Engineering and Applied Sciences, 6(1):71–78, 2011. [14] Y. Chen, C. Qiao, and X. Yu. Optical burst switching: a new area in optical networking research. Network, IEEE, 18(3):16–23, 2004. [15] Y. Chen, J. S. Turner, and P. F. Mo. Optimal burst scheduling in optical burst switched networks. Journal of Lightwave Technology, 25(8):1883–1894, 2007. [16] M. Demange, T. Ekim, and D. De Werra. (p, k)-coloring problems in line graphs. Theoretical Computer Science, 349(3):462–474, 2005. [17] K. Dolzer, C. Gauger, J. Spa¨th, and B. Stefan. Evaluation of reservation mechanisms for optical burst switching. AEU-International Journal of Electronics and Communications, 55(1):18–26, 2001. [18] F.-F. Dong, X.-L. Yang, S. Huang, X.-L. Duan, and K.-P. Long. Efficient data chan- nel rescheduling algorithm based on virtual burst for OBS networks. Guangdianzi Jiguang/Journal of Optoelectronics Laser, 19(7):909–913, 2008. [19] V. Eramo, M. Listanti, and P. Pacifici. A comparison study on the number of wavelength converters needed in synchronous and asynchronous all-optical switching architectures. Journal of Lightwave Technology, 21(2):340–355, 2003. [20] G. B. Figueiredo, E. Candido Xavier, and N. L. S. D. Fonseca. Optimal algorithms for the batch scheduling problem in OBS networks. Computer Networks, 56(14):3274–3286, 2012. [21] G. B. Figueiredo and N. L. S. Da Fonseca. Algorithm with linear computational com- plexity for batch scheduling in OBS networks. In IEEE International Conference on Communications, 2011. [22] G. B. Figueiredo, E. C. Xavier, and N. L. S. da Fonseca. An Optimal Batch Scheduling Algorithm for OBS Networks. GLOBECOM 2009 - 2009 IEEE Global Telecommunica- tions Conference, pages 1–6, 2009. 106 [23] K. Giaro, M. Kubale, and P. Obszarski. A graph coloring approach to scheduling of mul- tiprocessor tasks on dedicated machines with availability constraints. Discrete Applied Mathematics, 157(17):3625–3630, 2009. [24] C. Gico. Optical burst switching: a new area in optical networking research. IEEE Network, 18(3):16–23, 2004. [25] Y. Z. H. Zheng, C. Chen. MWIS-OS: Optimization Scheduling for OBS Networks. IEEE Communications Letters, 2006. [26] M. F. Hayat, F. Z. Khan, and H. R. van As. Performance model for an OBS node with a shared wavelength converter pool and an FDL buffer per link. Optical Network Design and Modeling (ONDM), 2011 15th International Conference on, pages 1–6, 2011. [27] B. Hirosaki, K. Emura, S.-i. Hayano, and H. Tsutsumi. Next-Generation Optical Network as a Value Creation Platform. IEEE Communications Magazine, 41(9):65–71, 2003. [28] Z. Hongyun, C. Changjia, and Z. YongXiang. Delayed burst segmentation for multi-hop optical burst switching networks, volume 2. 2009. [29] S. Huang, K.-P. Long, X.-L. Yang, and Q.-B. Chen. Data-burst batch-scheduling algorithm based on LAUC for optical burst switching networks. Bandaoti Guang- dian/Semiconductor Optoelectronics, 28(3):399 – 402+405, 2007. [30] M. Iizuka, M. Sakuta, Y. Nishino, and I. Sasase. A scheduling algorithm minimizing voids generated by arriving bursts in optical burst switched wdm network. In Global Telecommunications Conference, 2002. GLOBECOM’02. IEEE, volume 3, pages 2736– 2740. IEEE, 2002. [31] K. Janicki, P. Mrozicki, and P. Wiatr. Management platform for next generation optical networks. 2009. [32] J. P. Jue and V. M. Vokkarane. Optical burst switched networks. Springer Science & Business Media, 2006. [33] A. Kaheel and H. Alnuweiri. Batch scheduling algorithms for optical burst switching networks. Lecture notes in computer science, 3462:90–101, 2005. [34] B. Kantarci and S. Oktug. Adaptive threshold based burst assembly in OBS networks. In Canadian Conference on Electrical and Computer Engineering, pages 1419–1422, 2007. [35] M. Klinkowski, D. Careglio, J. Solé-Pareta, and M. Marciniak. Performance overview of the offset time emulated OBS network architecture, 2009. 107 [36] S. K. Lee, K. Sriram, H. S. Kim, and J. S. Song. Contention-based limited deflection routing protocol in optical burst-switched networks. IEEE Journal on Selected Areas in Communications, 23(8):1596–1610, 2005. [37] K. H. Liu. Wdm optical networks. IP Over WDM, pages 99–154, 2002. [38] M. Ljolje, R. Inkret, and B. Mikac. A comparative analysis of data scheduling algorithms in optical burst switching networks. In 2005 Conference on Optical Network Design and Modeling, 2005. [39] A. Mandloi and V. Mishra. A segmentation based channel scheduling scheme for im- proving channel utilization in OBS networks. Optik, 125(10):2437–2441, 2014. [40] A. Muhammad Umaru, M. S. Abd Latiff, and Y. Coulibaly. Segmentation-based on- demand burst rescheduling algorithm for optical burst switched networks. International Journal of Computer Communications and Networks (IJCCN), 1(1), 2011. [41] R. Nakkeeran, C. Balaji, N. Gujju, K. Balakumaran, and M. K. Sasidharan. Enhanced Burst Assembly Mechanism with Hybrid Signaling Scheme for Optical Burst Switched Networks. Advanced Computing and Communications, International Conference on, 0:727–732, 2007. [42] M. Nandi, A. K. Turuk, D. K. Puthal, and S. Dutta. Best fit void filling algorithm in Optical Burst Switching networks. In 2009 2nd International Conference on Emerging Trends in Engineering and Technology, ICETET 2009, pages 609–614, 2009. [43] K. Narayanaswamy, N. Kurahatti, and T. Srinivas. Just-in-time signaling with modi- fied architecture for optical burst switching WDM networks. 2006 IFIP International Conference on Wireless and Optical Communications Networks, 2006. [44] C. T. Ng, T. C. E. Cheng, A. M. Bandalouski, M. Y. Kovalyov, and S. S. Lam. A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines. Journal of the Operational Research Society, 65(10):1571–1579, 2014. [45] O. Pedrola, S. Rumley, D. Careglio, M. Klinkowski, P. Pedroso, J. Solé-Pareta, and C. Gaumier. A performance survey on deflection routing techniques for OBS networks. In ICTON 2009: 11th International Conference on Transparent Optical Networks, 2009. [46] C. Qiao and M. Yoo. Optical Burst Switching (OBS) - A New Paradigm for an Optical Internet. Journal of High Speed Networks, 8(716):69–84, 1999. 108 [47] J. J. Rodrigues and B. Vaidya. Evaluation of resource reservation protocols for IP over OBS networks. In ICTON 2009: 11th International Conference on Transparent Optical Networks, 2009. [48] K. Seklou, A. Sideri, P. Kokkinos, and E. Varvarigos. New assembly techniques and fast reservation protocols for optical burst switched networks based on traffic prediction. Optical Switching and Networking, 10(2):132–148, 2013. [49] D. M. Shan, K. C. Chua, and G. Mohan. On burst rescheduling in OBS networks with partial wavelength conversion capability. Computer Networks, 54(5):706–715, 2010. [50] R. Shenai, S. Gowda, and K. Sivalingam. Oirc obs-ns simulator, 2006. [51] S. Singh et al. Priority based burst assembly for optical burst switched network. Indian Journal of Science and Technology, 9(48), 2016. [52] D. Spielman. Spectral Graph Theory and its Applications. 48th Annual IEEE Sympo- sium on Foundations of Computer Science (FOCS’07), pages 29–38, 2007. [53] D. Tafani, C. McArdle, and L. Barry. Optimal allocation of fibre delay lines in optical burst switched networks. In AICT 2012 - 8th Advanced International Conference on Telecommunications, 2012. [54] C.-W. T. C.-W. Tan, M. Gurusamy, and J.-S. Lui. Achieving proportional loss differ- entiation using probabilistic preemptive burst segmentation in optical burst switching WDM networks. IEEE Global Telecommunications Conference, 2004. GLOBECOM ’04., 3, 2004. [55] S. K. Tan, G. Mohan, and K. C. Chua. Algorithms for burst rescheduling in {WDM} optical burst switching networks. Computer Networks, 41(1):41–55, 2003. [56] S. K. Tan, G. Mohan, and K. C. Chua. Burst rescheduling with wavelength and last-hop fdl reassignment in wdm optical burst switching networks. In Communications, 2003. ICC’03. IEEE International Conference on, volume 2, pages 1448–1452. IEEE, 2003. [57] W. Tan, S. Wang, and L. Li. Burst segmentation for void-filling scheduling and its performance evaluation in optical burst switching. Optics express, 12(26):6615–6623, 2004. [58] W. Tang, F. Chen, M. Chen, and G. Liu. Flow scheduling in obs networks based on software-defined networking control plane. KSII Transactions on Internet & Information Systems, 10(1), 2016. 109 [59] J. Teng and G. N. Rouskas. Routing path optimization in optical burst switched net- works. In Optical Network Design and Modeling, 2005. Conference on, pages 1–10. IEEE, 2005. [60] M. Thachayani and R. Nakkeeran. Deflection Routing in OBS Networks. International Journal of Computer Applications Technology and Research, 2(3):340–344, 2013. [61] M. A. Toks??z and N. Akar. Dynamic threshold-based assembly algorithms for optical burst switching networks subject to burst rate constraints. Photonic Network Commu- nications, 20(2):120–130, 2010. [62] J. S. Turner. Terabit burst switching. Journal of High Speed Networks, 8(1):3–16, 1999. [63] T. Venkatesh, T. L. Sujatha, and C. S. R. Murthy. A novel burst assembly algorithm for optical burst switched networks based on learning automata. Optical Network Design And Modeling, Proceedings, 4534:368–377, 2007. [64] S. Verma, H. Chaskar, and R. Ravikanth. Optical Burst Switching: A Viable Solution for Terabit IP Backbone. IEEE Network, 14(6):48–53, 2000. [65] V. Vokkarane, J. Jue, and S. Sitaraman. Burst segmentation: an approach for reducing packet loss in optical burst switched networks. 2002 IEEE International Conference on Communications. Conference Proceedings. ICC 2002 (Cat. No.02CH37333), pages 2673–2677, 2002. [66] V. Vokkarane, Qiong Zhang, J. Jue, and Biao Chen. Generalized burst assembly and scheduling techniques for QoS support in optical burst-switched networks. Global Telecommunications Conference, 2002. GLOBECOM ’02. IEEE, 3:2747–2751, 2002. [67] V. M. Vokkarane and J. P. Jue. Segmentation-based nonpreemptive channel schedul- ing algorithms for optical burst-switched networks. Journal of Lightwave Technology, 23:3125–3137, 2005. [68] R. Wang, J. Chang, K. Long, and X. Yang. An efficient composite scheduling algorithm for optical burst switching networks. In First International Conference on Communica- tions and Networking in China, ChinaCom ’06, 2007. [69] J. Wei and J. McFarland, R.I. Just-in-time signaling for WDM optical burst switching networks. Journal of Lightwave Technology, 18(12):2019–2037, 2000. [70] G. J. Woeginger. On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130(1):5–16, 1994. 110 [71] J. Xu, C. Qiao, J. Li, and G. Xu. Efficient Burst Scheduling Algorithms in Optical Burst-Switched Networks Using Geometric Techniques. IEEE Journal on Selected Areas in Communications, 22(9):1796–1811, 2004. [72] J. H. Xu, C. M. Qiao, J. K. Li, and G. Xu. Efficient channel scheduling algorithms in optical burst switched networks. Ieee Infocom 2003: the Conference on Computer Communications, Vols 1-3, Proceedings, pages 2268–2278, 2003. [73] S. J. B. Yoo. Optical packet and burst switching technologies for the future photonic internet, 2006. [74] M. Zhang, X. Yang, and H. Liu. A data channel scheduling algorithm based on burst mi- gration for optical burst switching networks. In Proceedings of SPIE - The International Society for Optical Engineering, volume 5281, pages 678–686, 2003. [75] H. Zheng and C. Chen. Performance analysis of scheduling algorithms in optical burst switching (obs) networks. In Innovative Computing, Information and Control, 2007. ICICIC’07. Second International Conference on, pages 557–557. IEEE, 2007. 111