Tài liệu Phân tích và đánh giá hiệu năng một số cơ chế điều khiển tránh tắc nghẽn tại nút lõi trong mạng chuyển mạch chùm quang

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN ĐẶNG THANH CHƯƠNG PHÂN TÍCH VÀ ĐÁNH GIÁ HIỆU NĂNG MỘT SỐ CƠ CHẾ ĐIỀU KHIỂN TRÁNH TẮC NGHẼN TẠI NÚT LÕI TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN ĐẶNG THANH CHƯƠNG PHÂN TÍCH VÀ ĐÁNH GIÁ HIỆU NĂNG MỘT SỐ CƠ CHẾ ĐIỀU KHIỂN TRÁNH TẮC NGHẼN TẠI NÚT LÕI TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG Chuyên ngành: BẢO ĐẢM TOÁN HỌC CHO MÁY TÍNH VÀ HỆ THỐNG TÍNH TOÁN Mã số: 62.46.35.01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS Vũ Duy Lợi 2. TS Võ Viết Minh Nhật HÀ NỘI – 2013 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do chính tôi thực hiện. Các số liệu, kết quả trong luận án là trung thực và chưa được ai công bố trong bất kỳ công trình nào khác. Hà nội, tháng 12 năm 2013 Tác giả Đặng Thanh Chương LỜI CÁM ƠN Đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới Phó giáo sư, Tiến sĩ Vũ Duy Lợi và Tiến sĩ Võ Viết Minh Nhật, những người Thầy tâm huyết đã tận tình hướng dẫn, động viên khích lệ, giúp đỡ và dành nhiều thời gian trao đổi, định hướng cho tôi trong quá trình thực hiện Luận án. Tôi cũng gởi lời cảm ơn chân thành đến Giáo sư, Tiến sĩ khoa học Đỗ Văn Tiến tại Đại học Bách Khoa và Kinh tế Budapest, Hungary đã hỗ trợ, đóng góp nhiều ý kiến quý báu liên quan đến Luận án. Tôi xin gởi lời cám ơn chân thành tới Ban lãnh đạo Viện Công nghệ thông tin, Viện Hàn lâm và khoa học công nghệ Việt Nam, các Thầy cô giáo và các Phòng liên quan của Viện, đặc biệt là các Thầy Đặng Văn Đức, Thầy Nguyễn Văn Tam và Thầy Phạm Thanh Giang đã tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu. Con xin bày tỏ lòng biết ơn sâu sắc đến những người thân yêu nhất trong gia đình, đến hương hồn của Ba, đến Mẹ, những người suốt đời tận tụy, hi sinh cho các con. Cám ơn Vợ và Con gái, Con trai yêu đã ủng hộ, tạo điều kiện và giúp đỡ để Anh có thể yên tâm học tập, nghiên cứu. Cuối cùng, xin gởi lời cám ơn đến bạn bè thân thiết, đồng nghiệp tại Khoa CNTT, Khoa Toán, Trường Đại học Khoa học Huế đã cổ vũ, động viên tôi trong thời gian thực hiện Luận án. i MỤC LỤC MỤC LỤC........................................................................................................................................... i DANH MỤC CÁC THUẬT NGỮ ................................................................................................... iv DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT ................................................................................. v DANH MỤC HÌNH VẼ .................................................................................................................. viii DANH MỤC BẢNG ......................................................................................................................... xi MỞ ĐẦU............................................................................................................................................ 1 Chương 1 GIỚI THIỆU TỔNG QUAN .......................................................................................... 5 Mạng truyền dẫn quang và các công nghệ chuyển mạch quang ........................................ 5 1.1. 1.1.1. Chuyển mạch kênh quang .......................................................................................... 6 1.1.2. Chuyển mạch gói quang ............................................................................................. 6 1.1.3. Chuyển mạch chùm quang ......................................................................................... 7 Mạng chuyển mạch chùm quang........................................................................................ 7 1.2. 1.2.1. Đặc trưng chung của mạng chuyển mạch chùm quang .............................................. 7 1.2.2. Kiến trúc mạng chuyển mạch chùm quang ................................................................ 8 1.2.3. Cơ chế hoạt động trong mạng chuyển mạch chùm quang........................................ 11 1.2.3.1. Tập hợp chùm....................................................................................................... 11 1.2.3.2. Định tuyến chùm .................................................................................................. 13 1.2.3.3. Báo hiệu chùm...................................................................................................... 14 1.2.3.4. Lập lịch chùm....................................................................................................... 15 1.2.3.5. Xử lý tranh chấp chùm ......................................................................................... 16 Đánh giá hiệu năng trong mạng chuyển mạch chùm quang............................................. 21 1.3. 1.3.1. Đặt vấn đề ................................................................................................................ 21 1.3.2. Các nghiên cứu liên quan đến Luận án .................................................................... 22 1.3.3. Vấn đề nghiên cứu trong Luận án ............................................................................ 24 Kết luận chương ............................................................................................................... 25 1.4. Chương 2 ĐIỀU KHIỂN TRÁNH TẮC NGHẼN BẰNG ĐỊNH TUYẾN LỆCH HƯỚNG KẾT HỢP VỚI ĐƯỜNG TRỄ QUANG FDL ......................................................................................... 26 2.1. Định tuyến lệch hướng dựa trên giao thức báo hiệu JET ................................................. 26 2.2. Kiến trúc nút lõi OBS và nguyên tắc chuyển mạch ......................................................... 27 2.3. Mô hình phân tích cơ bản và các giả thiết ........................................................................ 29 2.3.1 Các giả thiết.............................................................................................................. 29 2.3.2 Mô hình phân tích cơ bản ......................................................................................... 30 ii 2.4. Mô hình định tuyến lệch hướng không có ưu tiên (mô hình DRNP) ............................... 31 2.5. Mô hình định tuyến lệch hướng có ưu tiên (mô hình DRWP) ......................................... 33 2.5.1. Lược đồ chuyển trạng thái và hệ phương trình trạng thái cân bằng ......................... 33 2.5.2. Tính toán xác suất tắc nghẽn .................................................................................... 35 2.5.3. Một số kết quả phân tích .......................................................................................... 38 2.6. Mô hình định tuyến lệch hướng có ưu tiên với đường trễ quang FDL (mô hình DRPF). 41 2.6.1. Lược đồ chuyển trạng thái và hệ phương trình trạng thái cân bằng ......................... 41 2.6.2. Tính toán xác suất tắc nghẽn .................................................................................... 45 2.6.3. Một số kết quả phân tích .......................................................................................... 46 2.7. Mô hình định tuyến lệch hướng 3 giai đoạn (mô hình DRND) ....................................... 49 2.7.1. Mô hình phân tích .................................................................................................... 49 2.7.2. Một số kết quả phân tích .......................................................................................... 54 2.8. Kết luận chương ............................................................................................................... 56 Chương 3 ĐIỀU KHIỂN TRÁNH TẮC NGHẼN BẰNG CHUYỂN ĐỔI BƯỚC SÓNG CÓ/KHÔNG CÓ SỰ LỆCH HƯỚNG ............................................................................................. 57 3.1. Mô hình và giả thiết chung............................................................................................... 57 3.2. Điều khiển tắc nghẽn dựa trên chuyển đổi bước sóng không xét sự lệch hướng ............. 58 3.2.1. Mô hình với kiến trúc nút lõi SPIL giới hạn chuyển đổi bước sóng ........................ 59 3.2.2. Mô hình với kiến trúc nút lõi SPL giới hạn bộ chuyển đổi bước sóng .................... 72 3.3. Điều khiển tắc nghẽn kiến trúc nút lõi SPL giới hạn chuyển đổi bước sóng có hỗ trợ khả năng lệch hướng (mô hình SPLDF) ............................................................................................. 78 3.3.1. Kiến trúc nút lõi và một số giả thiết bổ sung ........................................................... 78 3.3.2. Mô hình phân tích với giới hạn bộ chuyển đổi bước sóng ....................................... 79 3.3.3. Mở rộng mô hình phân tích với giới hạn vùng chuyển đổi bước sóng .................... 83 3.3.4. Thuật toán tính ma trận tốc độ chuyển trạng thái Q ................................................. 83 3.3.5. Một số kết quả phân tích .......................................................................................... 87 3.4. Kết luận chương ............................................................................................................... 90 Chương 4 CÁC MÔ HÌNH ĐIỀU KHIỂN TRÁNH TẮC NGHẼN VỚI LƯU LƯỢNG ĐẾN LÀ TỔNG QUÁT (GI) HAY NON-POISSON ..................................................................................... 91 4.1. Đặt vấn đề ........................................................................................................................ 91 4.2. Mô hình phân tích xác suất tắc nghẽn lưu lượng lệch hướng trên một cổng ra tại nút lõi OBS với lưu lượng non-Poisson .................................................................................................. 91 4.2.1. Một số giả thiết......................................................................................................... 92 4.2.2. Tính xác suất tắc nghẽn với lưu lượng non-Poisson bằng phương pháp xấp xỉ ERT .. .................................................................................................................................. 93 iii 4.2.3. Tính xác suất tắc nghẽn với lưu lượng lệch hướng là tổng quát GI bằng mô hình GI/M/ω/ω ................................................................................................................................. 95 4.2.4. Trường hợp đặc biệt với quá trình đến là quá trình Poisson ngắt ............................ 96 4.2.5. Phân tích kết quả ...................................................................................................... 99 4.3. Mô hình phân tích nút lõi OBS với các quá trình đến Renewal và Poisson................... 103 4.3.1. Một số giả thiết mở rộng ........................................................................................ 103 4.3.2. Mô hình phân tích .................................................................................................. 104 4.3.3. Độ trễ trung bình trong các đường trễ quang FDL ................................................. 105 4.3.4. Xác suất tắc nghẽn tại nút lõi OBS với các quá trình đến Renewal và Poisson ..... 108 4.3.5. Phân tích kết quả .................................................................................................... 112 4.4. Kết luận chương ............................................................................................................. 115 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ..................................................................................... 116 Danh mục các công trình của tác giả ............................................................................................. 118 Tài liệu tham khảo.......................................................................................................................... 120 iv DANH MỤC CÁC THUẬT NGỮ Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt Burst Chùm (quang) dữ liệu Burst Loss Probability Xác suất mất chùm Blocking Probability Xác suất tắc nghẽn Caried traffic Lưu lượng được mang Deflection Routing Định tuyến lệch hướng Infinitesimal generator matrix Ma trận tốc độ chuyển trạng thái tổng quát Lightpath Kênh quang Loss system Hệ thống tổn thất Mean Delay Độ trễ trung bình Mean value Giá trị kỳ vọng Mixed loss –delay system Hệ thống kết hợp tổn thất - trễ Multi-dimensional traffic model Mô hình lưu lượng đa chiều Offset time Khoảng cách (thời gian) giữa gói điều khiển và chùm dữ liệu Overflow traffic Lưu lượng tràn Quality of Service Chất lượng dich vụ Offered traffic Lưu lượng đến (cung cấp đến) Renewal process Quá trình hồi phục (đổi mới) Traffic Lưu lượng Deflection Traffic Lưu lượng lệch hướng Non-Deflection Traffic Lưu lượng không lệch hướng Traffic load Tải lưu lượng Variance value Giá trị phương sai v DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT Từ viết tắt Ký hiệu Diễn giải tiếng Anh Diễn giải tiếng Việt AONs All-Optical Networks Mạng toàn quang BCP Burst Control Packet Gói điều khiển chùm CCG Control Channel Group Nhóm kênh điều khiển CWC Complete Wavelength Conversion Chuyển đổi bước sóng hoàn toàn DB Data Burst Chùm dữ liệu DRNP Deflection Routing without Priority Định tuyến lệch hướng không xét độ ưu tiên DRWP Deflection Routing with Priority Định tuyến lệch hướng có xét độ ưu tiên DRPF Deflection Routing with Priority and FDL Định tuyến lệch hướng có xét độ ưu tiên với FDL DRND Deflection Routing “3-stage” “no drop” Định tuyến lệch hướng 3 giai đoạn DCG Data Channel Group Nhóm kênh dữ liệu ERT Equivalent Random Theory Lý thuyết ngẫu nhiên tương đương FCFS First Come First Service Đến trước phục vụ trước FDL Fiber Delay Line Đường trễ quang FWC Full Wavelength Conversion Chuyển đổi bước sóng với phân bố đầy đủ GoS Grade of Service Cấp độ dịch vụ General Independent distribution (renewal process) Phân phối tổng quát (quá trình đến độc lập) GMPLS Generalized Multiprotocol Label Switching Chuyển mạch nhãn đa giao thức tổng quát IP Internet Protocol Giao thức Internet IPP Interrupted Poisson Process Quá trình Poisson ngắt JET Just Enough Time Giao thức báo hiệu với thời gian đặt GI vi trước tài nguyên vừa đủ LAUT Lastest Available Unscheduled Time Thời gian chưa lập lịch khả dụng sau cùng nhất LCFS Last Come First Service Đến sau phục vụ trước LRWC Limited Range Wavelength Conversion Chuyển đổi bước sóng với vùng chuyển đổi có giới hạn Limited Share-per-in-Link Chuyển đổi bước sóng với vùng chuyển đổi có giới hạn với kiến trúc SPIL Markovian (Poisson process (or random) arrival process) Quá trình đến Poisson Markovian (Exponential service time) Phân phối mũ MMPP Markov Modulated Poisson Process Quá trình Poisson điều chế bởi Markov NFWC Non-Full Wavelength Conversion Chuyển đổi bước sóng với phân bố không đầy đủ OBS Optical Burst Switching Chuyển mạch chùm quang OBSNs Optical Burst Switching Networks Mạng chuyển mạch chùm quang OCS Optical Circuit Switching Chuyển mạch kênh quang OEO Optical-to-Electrical-to-Optical Chuyển đổi quang-điện-quang OPS Optical Packet Switching Chuyển mạch gói quang OPSNs Optical Packet Switching Networks Mạng chuyển mạch gói quang OTN Optical Transport Network Mạng truyền tải quang OXC Optical Cross Connect Thiết bị chuyển mạch (đấu chéo) quang PASTA Poisson arrivals see time average Tính chất PASTA PSPIL Partial Share-per-in-Link Giới hạn số bộ chuyển đổi bước sóng với kiến trúc SPIL PLSPIL Partial Limited Share-per-in-Link Giới hạn chuyển đổi bước sóng với kiến trúc SPIL Partial Wavelength Converters Giới hạn số bộ chuyển đổi bước sóng (Chuyển đổi bước sóng với phân bố một phần) LSPIL M PWC vii Infinitesimal generator matrix Ma trận tốc độ chuyển trạng thái tổng quát QoS Quality of Service Chất lượng dịch vụ RAM Random Access Memory Bộ nhớ truy cập ngẫu nhiên RWA Routing and Wavelength Allocation Định tuyến và phân phối bước sóng SCU Switching Control Unit Đơn vị điều khiển chuyển mạch SPL Share-per-Link Chia s trên mỗi kết nối ra SPLDF Share-per-Link Deflection Mô hình SPL hỗ trợ sự lệch hướng SPIL Share-per-in-Link Chia s trên mỗi kết nối vào SPN Share-per-Node Chia s trên toàn nút lõi TE Traffic Engineering Kỹ thuật lưu lượng WC Wavelength Converters Bộ chuyển đổi bước sóng WDM Wavelength Division Multiplexing Kỹ thuật ghép kênh bước sóng WR Wavelength Router Bộ định tuyến bước sóng WRNs Wavelength-Routed Networks Mạng định tuyến bước sóng Q viii DANH MỤC HÌNH VẼ Hình 1.1. Sự phát triển của mạng quang ............................................................................... 5 Hình 1.2. Kiến trúc của mạng chuyển mạch chùm quang ..................................................... 9 Hình 1.3. Kiến trúc nút biên vào mạng OBS ....................................................................... 10 Hình 1.4. Kiến trúc nút lõi OBS ........................................................................................... 10 Hình 1.5. Tập hợp và phân tách chùm ................................................................................. 11 Hình 1.6. Tập hợp chùm theo ngưỡng thời gian .................................................................. 12 Hình 1.7. Tập hợp chùm theo ngưỡng kích thước (số gói tối đa) ........................................ 12 Hình 1.8. Tập hợp chùm theo ngưỡng thời gian và ngưỡng độ dài chùm ........................... 12 Hình 1.9. Ví dụ về giao thức đặt trước tài nguyên JET ....................................................... 15 Hình 1.10. Mô tả định tuyến lệch hướng ............................................................................. 17 Hình 1.11. Làm trễ chùm bằng đường trễ quang FDL ........................................................ 18 Hình 1.12. Mô tả chuyển đổi bước sóng λ1 qua λ 2 .............................................................. 19 Hình 2.1. Mô hình mạng OBS với nút lõi C có tranh chấp ở một cổng ra .......................... 26 Hình 2.2. Giao thức báo hiệu JET với định tuyến lệch hướng ............................................ 27 Hình 2.3. Nút lõi kiến trúc SPL (share-per-link) với CWC và FDL truyền thẳng ............... 28 Hình 2.4. Nút lõi kiến trúc share-per-link (SPL) với CWC và FDL hồi quy ....................... 28 Hình 2.5. Mô hình phân tích cơ bản tại nút lõi OBS ........................................................... 31 Hình 2.6. Lược đồ chuyển trạng thái tại nút lõi OBS không x t QoS (mô hình D NP)...... 32 Hình 2.7. Lược đồ chuyển trạng thái tại nút lõi OBS với QoS (mô hình DRWP) ............... 34 Hình 2.8. Xác suất tắc nghẽn các chùm lệch hướng tương ứng với mô hình D NP và D WP, ω = 16, ωS = 6 ........................................................................................................ 38 Hình 2.9. Xác suất tắc nghẽn các chùm lệch hướng tương ứng với mô hình D WP, ω = 16, ωS= 6, 8, 10, 12.................................................................................................................... 39 Hình 2.10. Xác suất tắc nghẽn trung bình của giai đoạn cuối cùng trong mô hình (B3_ ) và mô hình đề xuất D WP (PBII_DRWP), ω=16, ωS = 12, k = 4, n = 1 .............. 40 Hình 2.11. Mô hình 2 giai đoạn với FDL có x t QoS (mô hình D PF) .............................. 41 Hình 2.12. Lược đồ chuyển trạng thái tại nút lõi OBS với QoS tại giai đoạn 2 - mô hình DRPF ................................................................................................................................... 42 Hình 2.13. Xác suất tắc nghẽn của lưu lượng lệch hướng tại giai đoạn 2 mô hình D PF so sánh với mô hình trong 19 vs β ......................................................................................... 47 Hình 2.14. Xác suất tắc nghẽn tại giai đoạn 2 – so sánh giữa mô hình D PF và mô hình D WP (ρ2=0.7ρ) vs β .......................................................................................................... 47 Hình 2.15. Xác suất tắc nghẽn luồng lệch hướng tại giai đoạn 2 mô hình D PF - so sánh (2.1 ) với (2.1 a) vs β .......................................................................................................... 48 Hình 2.16. Xác suất tắc nghẽn tại giai đoạn 2 mô hình D PF - so sánh (2.1 ) với (2.19) vs β ........................................................................................................................................... 49 Hình 2.17. Mô hình phân tích với 3 giai đoạn (mô hình D ND) ........................................ 50 Hình 2.18. Lược đồ chuyển trạng thái ở giai đoạn 3 - mô hình DRND .............................. 51 Hình 2.19. Xác suất tắc nghẽn chùm trung bình PBDRND_d (PB_D ND_d) và PBd_pevac vs β ............................................................................................................................................. 54 Hình 2.20. Tổng xác suất tắc nghẽn chùm trung bình PBDRND (PB_D ND) và PBa_pevac vs β ............................................................................................................................................. 55 Hình 2.21. Tổng xác suất tắc nghẽn chùm trung bình PBDRND_0.3 (PB_DRND_0.3), PBDRND_0.4 (PB_ DRND _0.4) và PBDRND_0.5 (PB_ D ND _0. ) vs β .................................. 55 Hình 3.1. Nút lõi OBS kiến trúc SPIL với các bộ chuyển đổi bước sóng ............................ 59 ix Hình 3.2. Lược đồ chuyển trạng thái Markov 1-chiều tại nút lõi OBS kiến trúc SPIL ....... 59 Hình 3.3. Sự phân phối của các bước sóng đang sử dụng và sự tương ứng của số tập vùng chuyển đổi bị chiếm giữ hoàn toàn (biểu hiện bởi b). Trong ví dụ trên, ω = 8, r = 3, và k = 5.(a) b = 0; (b) b = 2 ({3, 4, 5}, {4, 5, 6}); (c) b = 1 ({7, 8, 1}); (d) b = 3 ({3, 4, 5}, {4, 5, 6}, {5, 6, 7}) ......................................................................................................................... 62 Hình 3.4. Không có tắc nghẽn với trường hợp số bước sóng bận nhỏ hơn giá trị vùng chuyển đổi (ω = , r = và k = 4) ...................................................................................... 62 Hình 3.5. Xác suất tắc nghẽn trong mô hình PSPIL với trường hợp (ω=16; C=0,4, ,16) vs β ........................................................................................................................................... 66 Hình 3.6. Xác suất tắc nghẽn trong mô hình PSPIL với trường hợp (ω=10, 16; C=4) vs β ............................................................................................................................................. 66 Hình 3.7. Xác suất tắc nghẽn trong mô hình LSPIL với trường hợp (ω = 1 ; r = 3, 7, 11, 1 ) vs β ................................................................................................................................. 67 Hình 3.8. Xác suất tắc nghẽn trong mô hình LSPIL với trường hợp (ω = 1 , 31; r = 9) vs β ............................................................................................................................................. 68 Hình 3.9. So sánh xác suất tắc nghẽn trong mô hình PSPIL với c = ω, trong mô hình LSPIL với r = ω, trong mô hình PLSPIL và mô phỏng với C = ω, r = ω (ω=1 ; C = 1 ; r=1 ) vs β............................................................................................................................. 68 Hình 3.10. So sánh xác suất tắc nghẽn trong mô hình PLSPIL với C = ω, r < ω và xác suất tắc nghẽn trong mô hình LSPIL với r < ω (ω = 1 ; r = 3) vs β .......................................... 69 Hình 3.11. Xác suất tắc nghẽn trong mô hình PLSPIL với r = ω, C < ω và trong mô hình PSPIL với C < ω (ω = 16;C = ) vs β ................................................................................. 69 Hình 3.12. Xác suất tắc nghẽn trong mô hình PLSPIL với trường hợp ω thay đổi, r và C không đổi (r < ω, C < ω) (ω =1 , 21, 31; r= ; C=6) vs β ................................................. 70 Hình 3.13. Xác suất tắc nghẽn trong mô hình PLSPIL với trường hợp ω và C không đổi (C < ω), r thay đổi (r < ω) (ω = 1 ; r = 7, 10; 13, C = 10) vs β ............................................ 70 Hình 3.14. Xác suất tắc nghẽn trong mô hình PLSPIL với trường hợp ω và r không đổi (r < ω), C thay đổi (C < ω) (ω = 1 ; r = 7; C = 13, 10, 4) vs β ............................................ 71 Hình 3.15. So sánh kết quả phân tích với kết quả mô phỏng ứng với mô hình PLSPIL đề xuất....................................................................................................................................... 71 Hình 3.16. Nút lõi OBS kiến trúc SPL với các bộ chuyển đổi bước sóng ............................ 72 Hình 3.17. Lược đồ chuyển trạng thái 2-chiều với mô hình kiến trúc nút lõi SPL .............. 73 Hình 3.18. Sơ đồ chuyển trạng thái đối với trạng thái ( ,c) ............................................... 74 Hình 3.19. Kiến trúc nút lõi OBS với hỗ trợ khả năng lệch hướng ..................................... 78 Hình 3.20. Sơ đồ chuyển trạng thái đối với trạng thái ( 1,c1; w2,c2) .................................. 79 Hình 3.21. Lược đồ chuyển trạng thái ứng với mô hình SPLDF ......................................... 81 Hình 3.22. Xác suất tắc nghẽn với ω=3, C=2 và p= 0,0. ,0.7,1 , τk=1 vs β ...................... 88 Hình 3.23. Xác suất tắc nghẽn theo p với β=0.4 và β=0. .................................................. 88 Hình 3.24. Xác suất tắc nghẽn - phân tích và mô phỏng ..................................................... 89 Hình 3.25. Xác suất tắc nghẽn theo p với ω=3; C=1,2,3; τk=1 vs β=0. ........................... 89 Hình 4.1. Phương pháp E T với lưu lượng non-Poisson .................................................... 94 Hình 4.2. Mô tả quá trình lưu lượng lệch hướng từ cổng 1 sang cổng 2 theo quá trình IPP ............................................................................................................................................. 97 Hình 4.3. Lược đồ chuyển trạng thái tại cổng ra 2 (ứng với quá trình đến IPP) ................ 97 Hình 4.4. Xác suất tắc nghẽn lưu lượng lệch hướng tại cổng ra 2 nút lõi OBS với ω cố định, p thay đổi .................................................................................................................. 100 x Hình 4.5. Xác suất tắc nghẽn nghẽn lưu lượng lệch hướng tại cổng ra 2 nút lõi OBS với ω thay đổi, K = 10 ................................................................................................................. 101 Hình 4.6. Xác suất tắc nghẽn lưu lượng lệch hướng tại cổng ra 2 nút lõi OBS với K thay đổi, ω = 12 ....................................................................................................................... 101 Hình 4.7. Xác suất tắc nghẽn nghẽn lưu lượng lệch hướng tại cổng ra 2 nút lõi OBS – so sánh giữa phân tích và mô phỏng ...................................................................................... 102 Hình 4.8. Lưu đồ tính xác suất tắc nghẽn theo mô hình phân tích cơ bản với trường hợp kết hợp lưu lượng GI và Poisson ............................................................................................. 104 Hình 4.9. Mô hình GI/M/L/L với các FDL (giai đoạn 1) ................................................... 106 Hình 4.10. Phương pháp E T với lưu lượng tràn bên trong các FDL .............................. 107 Hình 4.11. Phương pháp E T ứng với kết hợp 2 luồng lưu lượng GI và Poisson ............ 110 Hình 4.12. Xác suất tắc nghẽn tại giai đoạn 2 vs β ........................................................... 112 Hình 4.13. Xác suất tắc nghẽn giai đoạn 2 - theo phương pháp E T và GI vs β .............. 112 Hình 4.14. Xác suất tắc nghẽn của luồng lệnh hướng tại giai đoạn 2 vs β ....................... 113 Hình 4.15. Độ trễ trung bình của luồng lệnh hướng trong dãy FDL vs β ......................... 113 Hình 4.16. Xác suất tắc nghẽn giữa lưu lượng GI và lưu lượng Poisson vs β .................. 114 Hình 4.17. Xác suất tắc nghẽn với luồng lệnh hướng là Poisson – so sánh với mô hình D NP vs β .......................................................................................................................... 114 xi DANH MỤC BẢNG Bảng 2.1. Ma trận tổng quát Q (nSDRWP × nSDRWP) - mô hình DRWP ................................ 37 Bảng 2.2. Xác suất tắc nghẽn trung bình của 2 mô hình DRNP và DRWP khi ωS = ω ...... 39 Bảng 2.3. Xác suất tắc nghẽn của lưu lượng lệch hướng tại giai đoạn 2 - mô hình DRWP với ω = 16, ωS = 6, ρ2 = 0.3ρ ................................................................................................ 40 Bảng 2.4. Ma trận Q - Mô hình DRPF................................................................................. 44 Bảng 2.5. Ma trận Q(0) - Mô hình DRPF ............................................................................. 44 Bảng 2.6. Xác suất tắc nghẽn tại giai đoạn 2 - mô hình DRPF - so sánh với trong [19] khi ωS = ω = 16 vs β................................................................................................................... 48 Bảng 3.1. Ma trận tổng quát Q (nS × nS ) - Mô hình SPL-PWC .......................................... 76 Bảng 3.2. Quy luật chuyển đổi giữa chỉ số i trong ma trận Q và các trạng thái (w1,c1;w2,c2) ............................................................................................................................................. 84 Bảng 3.3. Ma trận tổng quát Q ((nS*nS) x (nS*nS)).............................................................. 84 Bảng 3.4. Ma trận QQJj (0 ≤ j ≤ C) có kich thước ((ω+1-j)*nS) x (ω+1-j)*nS)) ................. 85 Bảng 3.5. Ma trận QQ (0 ≤ j ≤ C) có kich thước (nS x nS) .................................................. 85 Bảng 3.6. Ma trận Bj2 (0 ≤ j ≤ C-1) có kích thước ((ω + 1 – j)*nS x (ω – j)*nS) ................. 86 Bảng 3.7. Xác suất tắc nghẽn với ω=4, C=2, r thay đổi ...................................................... 90 Bảng 4.1. Xác suất tắc nghẽn của lưu lượng lệch hướng tính theo phương pháp ERT ..... 100 Bảng 4.2. Xác suất tắc nghẽn của lưu lượng lệch hướng tính theo các phương trình (4.21) và (4.27) ............................................................................................................................. 102 1 MỞ ĐẦU 1. Dẫn nhập Tốc độ phát triển nhanh của Internet 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ụ thông tin, làm gia tăng không ngừng nhu cầu về băng thông mạng. Ðiều này đòi hỏi phải xây dựng và phát triển những công nghệ truyền thông có dung lượng băng thông cao. Kỹ thuật truyền dẫn quang được xem là một công nghệ hứa hẹn bởi tốc độ truyền dữ liệu nhanh, khả năng băng thông tiềm năng lớn và mức độ lỗi tín hiệu nhỏ. Với một số thành tựu đạt được hiện nay của kỹ thuật ghép kênh bước sóng WDM, mạng truyền dẫn quang đã trở thành là một giải pháp hoàn hảo đáp ứng với xu hướng bùng nổ nhu cầu băng thông trên Internet hiện nay. Lịch sử phát triển của mạng truyền dẫn quang đã trải qua các giai đoạn, từ mạng chuyển mạch kênh quang OCS, chuyển mạch chùm quang OBS và chuyển mạch gói quang OPS. Thực tế, mô hình chuyển mạch gói quang OPS là mục tiêu hướng đến của các nhà phát triển mạng quang, tuy nhiên nó chưa thể trở thành hiện thực bởi hạn chế của công nghệ quang hiện nay là không thể sản xuất được các bộ đệm quang (tương tự như bộ nhớ RAM điện tử) cần sử dụng trong mô hình mạng chuyển mạch gói OPS. Một thỏa hiệp hiện nay là mô hình mạng chuyển mạch chùm OBS, bởi nó dung hòa được các ưu điểm của mô hình chuyển mạch kênh OCS và mô hình chuyển mạch gói OPS. Hơn nữa mạng OBS không yêu cầu các bộ đệm quang và do đó trong suốt với tầng điều khiển. Có thể nói các nhóm tác giả Harry Perros (và các đồng sự) và C. Qiao (và các đồng sự) là hai trong những người đầu tiên đề xuất mô hình mạng chuyển mạch chùm quang OBS với bài báo lần lượt trong [63] và [73], được xem là cơ sở cho các nghiên cứu sau này. Xuất phát từ các ý tưởng trong các bài báo này, rất nhiều vấn đề đã được đặt ra và nghiên cứu trong mạng OBS, như các bài toán về tập hợp chùm [20][36][48][59][60][77], các bài toán về lập lịch [29][37][41-43][53][70], các bài toán về báo hiệu [18][34][57], các bài toán về giải quyết tranh chấp (tắc nghẽn) [13][16][19][28][30][31][38][46][56][58][69][71-72], hay các bài toán về QoS [16][17][54]… Trên thế giới, nhiều luận án tiến sĩ về mạng chuyển mạch chùm quang OBS cũng đã được hoàn thành [14] [25][35][47][55][62][68], trong đó có các luận án liên quan đến vấn đề giải quyết tắc nghẽn trong mạng OBS, như luận án của tác giả Hailong Li trong [39] nghiên cứu một số phương pháp chuyển đổi bước sóng, luận án của tác giả J.Lambert trong [33] nghiên cứu một số phương pháp sử dụng đường trễ quang FDL, luận án của tác giả Daniele Tafani năm 2012 [25] 2 nghiên cứu phương pháp FDL và chuyển đổi bước sóng sử dụng lý thuyết tràn, hay một số nghiên cứu kênh tràn của tác giả Pratibha Menon trong [55]… Với tốc độ giao tiếp và nhu cầu sử dụng băng thông mạng ngày càng cao như hiện nay thì vấn đề đặt ra là làm thế nào để tăng tốc độ truyền tin, lượng thông tin có thể truyền tải nhanh nhất mà không xảy ra tình trạng tắc nghẽn. Vì vậy, tắc nghẽn chùm được xem là một vấn đề thách thức trong mạng chuyển mạch chùm quang. Sự tắc nghẽn chùm trong mạng OBS có thể xảy ra khi hai hay nhiều chùm từ các cổng vào khác nhau cố gắng đi ra trên cùng một cổng ra tại cùng một thời điểm. Nếu với mạng IP, một vùng đệm điện tử RAM sẽ được sử dụng để lưu tạm thời các gói tin IP có độ ưu tiên thấp hơn và sau đó được truyền đi khi cổng ra tương ứng rỗi. Tuy nhiên, công nghệ quang hiện nay không cho phép tạo ra các bộ đệm quang tương tự như vậy và do đó, chùm quang có độ ưu tiên thấp hơn sẽ bị loại bỏ. Các giải pháp cho việc xử lý tắc nghẽn hiện nay trên mạng OBS là: hoặc sử dụng đường trễ quang FDL để làm trễ chùm quang có độ ưu tiên thấp hơn [2125][33][65][71][76]; hoặc thực hiện chuyển đổi bước sóng đối với một trong hai chùm quang tranh chấp này [13][28][38][39][46][49][51][56][58]; hoặc định tuyến chùm quang có độ ưu tiên thấp hơn đến một cổng ra rỗi khác và sau đó truyền đi theo một đường truyền khác để đến đích (gọi là định tuyến lệch hướng) [15][19][28][61]; hoặc phân đoạn chùm [54][69]. Nhiều hướng tiếp cận riêng l cũng như kết hợp các giải pháp này cũng đã được nghiên cứu và đề xuất [15][19][28][29][58][72][74]. Trong Luận án này, chúng tôi tập trung nghiên cứu, xây dựng các mô hình toán học nhằm mô hình hóa các cơ chế điều khiển tránh tắc nghẽn tại nút lõi mạng OBS với các kiến trúc nút lõi khác nhau; trên cơ sở đó đánh giá hiệu năng nút lõi mạng thông qua các độ đo hiệu năng phù hợp, như xác suất tắc nghẽn (hay xác suất mất chùm), độ trễ chùm. Các mô hình phân tích trong Luận án tập trung thực hiện tại nút lõi OBS với một hoặc nhiều cổng ra với nhiều kiến trúc khác nhau theo các tài nguyên nút mạng như bộ chuyển đổi bước sóng WC hay các đường trễ quang FDL. Luận án tập trung vào nghiên cứu ba vấn đề chính, ứng với ba bài toán mà chúng tôi đã đặt ra từ ban đầu: Bài toán 1. Đề xuất, cải tiến mô hình toán học phân tích ảnh hưởng của định tuyến lệch hướng kết hợp với đường trễ quang FDL. Bài toán 2. Đề xuất, cải tiến mô hình kết hợp định tuyến lệch hướng với các khả năng chuyển đổi bước sóng, có tính đến các tham số ràng buộc, như khả năng 3 chuyển đổi bước sóng hoàn toàn (full), chuyển đổi bước sóng từng phần (partial), hay giới hạn vùng chuyển đổi bước sóng (limited). Bài toán 3. Mở rộng một mô hình trong bài toán 1 với trường hợp lưu lượng đến là không Poisson (lưu lượng tổng quát hay quá trình đến Renewal). 2. Mục tiêu nghiên cứu Mục tiêu của Luận án là nghiên cứu xây dựng các mô hình toán học (dựa trên lý thuyết hàng đợi – mô hình Markov và non-Markov) nhằm mô hình hoá một số cơ chế điều khiển tránh tắc nghẽn tại nút lõi mạng chuyển mạch chùm quang. Từ đó, phân tích, đánh giá, so sánh hiệu quả hoạt động của các cơ chế điều khiển tránh tắc nghẽn đề xuất dựa trên xác suất mất chùm (xác suất tắc nghẽn) tại mỗi nút lõi OBS, với các cơ chế đã được đề xuất trước đây. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của Luận án là mô hình nút lõi OBS với các kiến trúc khác nhau với các phân bố khác nhau của các bộ chuyển đổi bước sóng và các đường trễ quang FDL. Phạm vi nghiên cứu của Luận án tập trung vào các bài toán điều khiển tránh tắc nghẽn tại nút lõi OBS dựa trên các phương pháp truyền thống là chuyển đổi bước sóng, sử dụng đường trễ quang FDL và định tuyến lệch hướng. Ngoài ra, Luận án cũng nghiên cứu áp dụng phương pháp xây dựng ma trận tốc độ chuyển trạng thái ứng với các mô hình đề xuất. 4. Phương pháp nghiên cứu Phương pháp nghiên cứu chính của Luận án là phương pháp mô hình hóa giải tích. Theo đó, một số mô hình hàng đợi Markov [10][51][39][64][66-67][75] sẽ được áp dụng, so sánh với các kết quả đã được công bố trước đây và mở rộng với mô hình non-Markov trong trường hợp đơn giản [8-12][44-45][50]. Trong một số trường hợp, phương pháp mô phỏng (cho các mô hình hàng đợi tại nút lõi) [10] cũng sẽ được áp dụng để kiểm chứng kết quả tính toán của phương pháp phân tích, từ đó khẳng định tính đúng đắn của kết quả nghiên cứu. 5. Cấu trúc luận án Ngoài phần Mở đầu và Kết luận, Luận án bao gồm bốn chương nội dung. Chương 1 trình bày các khái niệm cơ bản về mạng chuyển mạch chùm quang, các hướng tiếp cận nghiên cứu của các tác giả trước đây, cũng như các hướng mở rộng mà chúng tôi sẽ thực hiện trong Luận án. Các đóng góp chính của Luận án được trình bày trong Chương 2, Chương 3 và Chương 4, bao gồm đề xuất một số mô hình 4 phân tích các cơ chế điều khiển tránh tắc nghẽn trong mạng OBS trên cơ sở cải tiến một số mô hình đã được nghiên cứu trước đây. Chương 2 trình bày các kết quả nghiên cứu các mô hình phân tích trong trường hợp sử dụng định tuyến lệch hướng với sự hỗ trợ của các đường trễ quang FDL [3][5][26]. Trên cơ sở các mô hình phân tích được công bố [13][19][28][58], chúng tôi thực hiện cải tiến, đề xuất mô hình mới nhằm nâng cao hiệu năng tại nút lõi mạng. Chương 3 trình bày các mô hình phân tích với chuyển đổi bước sóng (full, partial, limited) với có/không khả năng định tuyến lệch hướng [1][2][27]. Ngoài ra, trong Chương 3 cũng đề xuất một số thuật toán xây dựng ma trận tốc độ trạng thái Q ứng với mỗi mô hình nhằm tính các xác suất trạng thái cân bằng [1][27]. Phương pháp phân tích chính trong Chương 2 và Chương 3 là sử dụng các mô hình chuỗi Markov một chiều (one-dimensional) và đa chiều (two-dimensional và four-dimensional), tức là xem xét các lưu lượng đến tại nút lõi đều tuân theo phân phối Poisson. Việc mở rộng với các trường hợp non-Markov (ứng với lưu lượng tổng quát ) sẽ được xem xét trong Chương 4 trên cơ sở một số mô hình đã được phân tích trong Chương 2 và Chương 3. Theo đó, chúng tôi xem xét lưu lượng đến là lưu lượng tổng quát (quá trình Renewal) [6], cũng như phân tích với trường hợp kết hợp cả hai luồng lưu lượng Poisson và lưu lượng (non-Poisson) [7]. Mô hình phân tích khi đó không còn hoàn toàn là mô hình Markov và phương pháp được sử dụng là các phương pháp xấp xỉ và phương pháp xấp xỉ [7]. Kết quả phân tích trong trường hợp này (lưu lượng ) cũng được so sánh với kết quả trong mô hình ứng với tất cả đều là lưu lượng Poisson để đánh giá tính đúng của mô hình mở rộng. Cuối cùng, phần kết luận nêu những đóng góp của Luận án, hướng phát triển và những vấn đề quan tâm của tác giả. 5 Chương 1 GIỚI THIỆU TỔNG QUAN 1.1. Mạng truyền dẫn quang và các công nghệ chuyển mạch quang Phương thức truyền tải quang Xu thế phát triển mạng hiện nay trên thế giới và ở Việt Nam là xây dựng mạng truyền tải quang OTN cho Internet thế hệ mới dựa trên công nghệ WDM. Những nỗ lực phi thường về công nghệ truyền dẫn quang trong đó tập trung vào việc nghiên cứu các vấn đề công nghệ mạng WDM trên thế giới hiện nay đang dần đáp ứng được nhu cầu phát triển tất yếu của mạng. Có nhiều vấn đề cần phải giải quyết trong mạng OTN nhằm ngày càng hoàn thiện các chức năng của mạng. Trong các vấn đề đó, chuyển mạch quang trong mạng OTN được coi là những hướng đi hấp dẫn và có ý nghĩa. Một mặt, kỹ thuật này cho phép xây dựng được mạng truyền dẫn quang linh hoạt và bảo đảm thông suốt các lưu lượng tín hiện lớn. Mặt khác nó cho phép nâng cao tính thông minh cho lớp quang trong khi vẫn đơn giản hoá được rất nhiều cấu trúc mạng. Điều đó có tác động lớn tới việc xây dựng, khai thác và bảo dưỡng mạng có hiệu quả sau này. Về nguyên lý, một mạng chuyển mạch thực hiện chuyển lưu lượng từ một cổng vào hoặc kết nối lưu lượng trên một khối chuyển mạch tới một cổng ra. Hệ thống chuyển mạch quang là một hệ thống chuyển mạch cho phép các tín hiệu bên trong các sợi quang hay các mạch quang tích hợp được chuyển mạch có lựa chọn từ một mạch này tới một mạch khác. Sự phát triển của mạng quang WDM có thể được phân loại như Hình 1.1 [32][63][73]. Mạng chuyển mạch gói quang Mạng lưới chuyển mạch chùm quang Mạng vòng chuyển mạch chùm quang AONs Mạng lưới định tuyến bước sóng Mạng vòng định tuyến bước sóng Mạng WDM điểm-điểm Yêu cầu OEO Thời gian Hình 1.1. Sự phát triển của mạng quang