Tài liệu 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 (tt)

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN HỒNG QUỐC NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP LẬP LỊCH TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 62.48.01.01 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: 1. PGS.TS. Võ Viết Minh Nhật 2. TS. Nguyễn Hoàng Sơn HUẾ, NĂM 2017 Công trình này được hoàn thành tại: Trường Đại học Khoa học - Đại học Huế Người hướng dẫn khoa học: 1. PGS. TS. Võ Viết Minh Nhật, Đại học Huế 2. TS. Nguyễn Hoàng Sơn, Trường Đại học Khoa học, Đại học Huế Phản biện 1: GS. TS. Nguyễn Thúc Hải Trường Đại học Bách khoa Hà Nội Phản biện 2: GS. TS. Đặng Quang Á Viện Công nghệ Thông tin, Viện Hàn lâm KH&CN Việt Nam Phản biện 3: PGS. TS. Hồ Sỹ Đàm Trường Đại học Công nghệ, ĐHQG Hà Nội Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp Đại học Huế họp tại Đại học Huế vào lúc ...... giờ ..... ngày ..... tháng ..... năm 2018 Có thể tìm hiểu luận án tại thư viện: • Thư viện Quốc gia Việt Nam • Thư viện Trường Đại học Khoa học, Đại học Huế MỞ ĐẦU 1. Tính cấp thiết của đề tài 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: từ những mô hình định tuyến bước sóng (Wavelength-Routed, WR) 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, OPS) đượ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, 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, OBS) đã 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, BHP) được tách rời với phần (chùm) dữ liệu (Data Burst, DB). 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. 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ục đích chính của giải thuật lập lịch 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 lõi mạng, một trong các giải thuật lập lịch trực tiếp 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. 1 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 Trong số các giải thuật lập lịch trực tiếp, BF-VF 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à trong đó 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. 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 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 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 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. 2 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 • 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. Đó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 LGSVF[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. 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 1.2. Các mô hình chuyển mạch quang Các mô hình chuyển mạch quang có thể được chia thành 3 loại: chuyển mạch kênh quang, chuyển mạch gói quang và chuyển mạch chùm quang. 1.2.1. Chuyển mạch kênh quang 1.2.2. Chuyển mạch gói quang 1.2.3. Chuyển mạch chùm quang 1.3. Mạng chuyển mạch chùm quang Mạng OBS được xem như là một công nghệ hứa hẹn cho mạng Internet toàn quang thế hệ kế tiếp bởi nó có nhiều chức năng và ưu điểm hơn so với các mạng chuyển mạch quang khác. Một số đặc trưng của mạng OBS như sau: Tách biệt giữa kênh truyền gói điều khiển và kênh truyền chùm; Dành riêng một chiều; Độ dài chùm thay đổi được; Không cần bộ đệm quang. 1.3.1. Kiến trúc mạng OBS Một mạng OBS bao gồm các nút chuyển mạch chùm quang (nút OBS) kết nối với nhau bởi các sợi quang. Mỗi sợi quang có khả năng hỗ trợ các kênh đa bước sóng. Có hai kiểu nút trong mạng OBS: nút biên và nút lõi. 3 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 1.3.1.1. Cấu trúc nút biên 1.3.1.2. Cấu trúc nút lõi 1.3.2. Các hoạt động bên trong mạng OBS Các hoạt động bên trong mạng OBS bao gồm: tập hợp, báo hiệu, lập lịch và giải quyết tranh chấp. Mỗi hoạt động đều đóng vai trò quan trọng và tác động trực tiếp đến hiệu quả hoạt động của mạng OBS. 1.3.2.1. Tập hợp 1.3.2.2. Báo hiệu 1.3.2.3. Lập lịch 1.3.2.4. Định tuyến 1.4. Lập lịch trong mạng OBS 1.4.1. Giới thiệu bài toán lập lịch 1.4.2. Một số kiến thức liên quan 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, 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 và lập lịch nhóm. 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 đó. 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 loại: lập lịch không lấp đầy khoảng trống và lập lịch có lấp đầy khoảng trống. 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 4 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 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. 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ự, 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). 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, tác giả Umaru, Aydin và cộng sự đề 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 (Preemptive Channel Scheduling Algorithm) 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. Một 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. 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. 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. 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 1.4.3.4.1. Sử dụng đường trễ FDL 1.4.3.4.2. Chuyển đổi bước sóng 1.4.3.4.3. Định tuyến lệch hướng 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. 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 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 Trong chương này 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. 5 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 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 trống băng thông 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. 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. • 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-VF. • 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. 2.2.1. Giải thuật ODBR 2.2.2. Giải thuật ABR 2.2.3. Kỹ thuật phân đoạn chùm 2.2.4. Giải thuật SODBRA 2.2.5. Giải thuật PCSA 2.3. Giải thuật lập lịch kết hợp đề xuất iCSA Giải thuật lập lịch kết hợp được Luận án đề xuất iCSA (improved Composite Scheduling Algorithm) đã được công bố trong [CT2]. Giải thuật iCSA là một kết hợp của lập lịch lấp đầy khoảng trống, lập lịch lại và phân đoạn chùm, bao gồm 3 giai đoạn được thực hiện tuần tự tùy thuộc vào sự thành công hay thất bại của giai đoạn trước. Giai đoạn 1: Khi có một chùm đến, giải thuật lập lịch lấp đầy khoảng trống BFVF được gọi để tìm khoảng trống khả dụng vừa khít nhất để lập lịch cho chùm này. Nếu lập lịch thành công giải thuật iCSA kết thúc, ngược lại Giai đoạn 2 được gọi. Giai đoạn 2: lập lịch lại dựa trên một cải tiến của giải thuật ODBR. Đối với các chùm đã được lập lịch trước đó trên các kênh ra có chồng lấp với chùm đến sao cho khoảng băng thông nhàn rỗi được tạo ra có thể lập lịch được cho chùm đến. Trong trường hợp có nhiều hơn một kênh thỏa mãn, kênh mà có số chùm di chuyển ít nhất sẽ được chọn để lập lịch cho chùm đến. Nếu việc lập lịch lại không thành công, Giai đoạn 3 sẽ được gọi. 6 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 Giai đoạn 3: tính toán độ chồng lập của chùm đến với các chùm đã được lập lịch trên các kênh và kênh có khoảng chồng lấp nhỏ nhất sẽ được chọn để lập lịch cho chùm đến sau khi đã cắt phần chồng lấp; Nếu phần bị chồng lấp có thể được lập lịch trên một trong các kênh còn lại, một chùm mới sẽ được tạo ra và lập lịch trên kênh khả dụng đó(với giả sử nút lõi OBS có khả năng tạo gói điều khiển). Giải thuật iCSA được mô tả chi tiết như sau: Algorithm 2.1: iCSA (improved Composite Scheduling Algorithm) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Input : ub(sub , eub ), W = {1, 2, . . . , m}, SBk với k ∈ W ; Output: bestchannel ; bestchannel := BF V F (ub, W ); if (bestchannel 6= −1) then Lập lịch chùm ub trên kênh bestchannel và return; foreach k ∈ W do OBk := ∅; foreach sbi,k ∈ SBk do if (sub ∈ [si,k , ei,k ]) ∨ (si,k ∈ [sub , eub ]) then OBk := OBk ∪ {sbi,k }; refi,k := 0; else OB := OB ∪ {OBk }; Sort(k, |OBk |); k := 1; while (k ≤ m) do success := |OBk |; bestchannel := −1 ; foreach sbi,k ∈ SBk do bestchannel := BF V F (ub, W \ {k}); if (bestchannel 6= −1) then success := success − 1; refi,k := bestchannel; if (success = 0) then foreach sbi,k ∈ SBk do Lập lịch lại chùm sbi,k trên kênh k sang kênh refi,k ; Gửi lại gói điều khiển cho chùm sbi,k ; Gỡ bỏ chùm sbi,k lập lịch trên kênh k ; Lập lịch chùm ub trên kênh bestchannel và return; k := k + 1; k := 1; news := sub ; newe := eub ; droptype := −1; bestlenght := 0; bestchannel := −1; 7 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 while (k ≤ m) ∧ (|OBk | = 1) do if ((sub < s1,k ) ∧ (eub − s1,k ) < bestlenght) then bestlenght := eub − s1,k ; droptype := 0; bestchannel := k; else if ((sub > s1,k ) ∧ (eub − s1,k ) > bestlenght) then bestlenght := s1,k − eub ; droptype := 1; bestchannel := k; if (droptype = 0) then eub := eub − bestlenght; Lập lịch chùm ub sau khi loại bỏ đoạn đầu chồng lấp trên kênh bestchannel; eoverlap := eub ; soverlap := sub − bestlenght; Tạo chùm mới từ đoạn chồng lấp newub (soverlap , eoverlap ); ch := BF V F (newub , W ); if (ch 6= −1) then Lập lịch chùm newub trên kênh ch; Tạo gói điều khiển mới cho chùm newub và return; if (droptype = 1) then sub := sub − bestlenght; Lập lịch chùm ub sau khi loại bỏ đoạn đầu chồng lấp trên kênh bestchannel; eoverlap := eub ; soverlap := sub − bestlenght; Tạo chùm mới từ đoạn chồng lấp newub (soverlap , eoverlap ); ch := BF V F (newub , W ); if (ch 6= −1) then Lập lịch chùm newub trên kênh ch; Tạo gói điều khiển mới cho chùm newub và return; Function BFVF(ub, W ) 1 gap := ∞; 2 bestchannel := −1; 3 foreach k ∈ W do 4 e0,k := 0; e|SBk |+1,k := ∞; 5 foreach j ∈ SBk do 6 if ((sub > ej,k ) ∧ (sj+1,k > eub ) ∧ ((sj+1,k − ej,k ) < gap)) then 7 bestchannel := k; 8 gap := sj+1,k − ej,k ; 9 return bestchannel; Độ phức tạp của giải thuật iCSA: O(n × log(n)), n = max(|SBk |). 8 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 2.4. Mô phỏng và phân tích kết quả Để chứng minh tính hiệu quả của giải thuật đề xuất Luận án thực hiện cài đặt mô phỏng giải thuật lập lịch đề xuất iCSA để so sánh với các giải thuật đã được công bố, bao gồm LAUC, BFVF, ODBR, ABR, SODBRA và PCSA. Môi trường mô phỏng sử dụng gói NS2-obs0.9a và phần mềm C++, cài đặt trên máy tính CPU Intel Core 2 CPU 2.4 GHz, 2G RAM. Mô hình mạng mô phỏng NSFNET với 14 nút lõi, trong đó mỗi nút lõi kết nối với một nút biên. Qua kết quả mô phỏng được thể ở các Hình từ 2.8 đến 2.15 khi so sánh giải thuật lập lịch đề xuất iCSA và các giải thuật lập lịch đã được công bố cho thấy xác suất mất gói tin của giải thuật iCSA thấp hơn nhiều, giảm được số lượng gói điều khiển phải gửi lại do các chùm bị phân đoạn và có độ phức tạp giải thuật bằng với các giải thuật cùng loại. Hình 2.8. So sánh xác suất mất Hình 2.9. So sánh xác suất mất gói tin giữa LAUC và BF-VF gói tin giữa ODBR và ABR Hình 2.10. So sánh số chùm phải lập lịch lại giữa ODBR và ABR Hình 2.11. So sánh xác suất mất gói tin Hình 2.12. So sánh số chùm phải lập lịch lại của iCSA so với ODBR và ABR của iCSA so với ODBR và ABR Hình 2.13. So sánh xác suất mất gói tin của iCSA so với SODBRA và PSCA 9 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 Hình 2.14. So sánh số chùm lập lịch lại Hình 2.15. So sánh số chùm phân đoạn của iCSA so với SODBRA và PCSA của iCSA so với SODBRA và PCSA 2.5. Tiểu kết Chương 2 Chương này của Luận án đã trình bày, phân tích, đánh giá chi tiết các giải thuật lập lịch kết hợp giữa lập lịch trực tiếp và lập lịch lại ODBR, ABR và lập lịch trực tiếp kết hợp lập lịch lại và kỹ thuật phân đoạn chùm đã được công bố SODBRA, PSCA. Trên cơ sở phân tích, đánh giá và đưa ra ưu điểm và tồn tại của các giải thuật, Luận án đề xuất một giải thuật lập lịch trực tiếp kết hợp lập lịch lại và kỹ thuật phân đoạn chùm iCSA. Với những ưu điểm: • Giải thuật đề xuất iCSA sử dụng giải thuật lập lịch trực tiếp BFVF là giải thuật lập lịch tốt nhất trong các giải thuật lập lịch trực tiếp để lập lịch chùm đến. • Trong Giai đoạn 2, iCSA thực hiện lập lịch lại cho bất kỳ chùm chồng lấp nào với chùm đến nên giảm được xác suất mất gói tin và tận dụng băng thông tốt hơn. • Trong Giai đoạn 3, iCSA tìm khoảng trống (băng thông khả dụng) trên một kênh nào đó để lập lịch cho phần chùm chồng lấp này. Cách làm này sẽ làm giảm xác suất mất gói tin và sử dụng băng thông các kênh ra tốt hơn. Các kết quả 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 các giải thuật đã được công bố trước đó và có độ phức tạp giải thuật bằng với các giải thuật cùng loại. 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 3.1. Giới thiệu Lập lịch nhóm tại nút lõi OBS là hoạt động mà các gói điều khiển đến trong mỗi khe thời gian τ , dựa vào thông tin trong gói điều khiển một giải thuật lập lịch sẽ được gọi để tiến hành lập lịch đồng thời cho các chùm tương ứng của chúng (như thể hiện ở Hình 3.1). Lập lịch nhóm có thể được thực hiện chỉ trên một kênh dữ liệu ra khi không có sự hỗ trợ của chuyển đổi bước sóng và các chùm đến này được giả sử có cùng bước sóng. Loại lập lịch này được gọi là lập lịch nhóm trên đơn kênh. Trường hợp lập lịch nhóm có sự hỗ trợ của chuyển đổi bước sóng, được gọi là lập lịch nhóm trên đa kênh sẽ được trình bày trong chương tiếp theo. Nội dung tiếp theo của chương này sẽ tóm lược các giải thuật lập lịch nhóm trên đơn kênh đã được công bố trước đây. Trên cơ sở các phân tích và đánh giá những ưu điểm và tồn tại, từ đó Luận án đề xuất một số giải thuật lập lịch nhóm trên đa kênh nhằm nâng cao hiệu quả lập lịch. Kết quả cài đặt mô phỏng và phân tích cũng được mô tả chi tiết trong chương này. 10 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 Hình 3.1: (a) Mô tả hoạt động lập lịch nhóm trên đơn kênh và (b) đa kênh 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ố Có hai giải thuật lập lịch nhóm trên đơn kênh đã được công bố: OBS-GS(OBS Group Scheduling) và MWIS-OS(Maximum Weight Independent Set - Optimal Scheduling). 3.2.1. Giải thuật OBS-GS 3.2.2. Giải thuật MWIS-OS 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 3.3.1. Mô hình lập lịch nhóm trên đơn kênh Không mất tính tổng quát, giả sử xét một nút lõi OBS có 2 cổng vào, 2 cổng ra như Hình 3.6a, không sử dụng đường trễ FDL, không có các bộ chuyển đổi bước sóng và thời gian offset được thiết lập đủ để các gói điều khiển đặt trước và cấu hình các nút dọc theo hành trình từ nguồn đến đích. Hình 3.6b mô tả chi tiết mô hình lập lịch nhóm đề xuất. Các gói điều khiển đến trong khe thời gian τ được tính từ thời điểm gói điều khiển đầu tiên đến. Mô hình lập lịch nhóm có thể được mô tả thành quá trình 2 giai đoạn như sau: Hình 3.6. Mô hình hoạt động của lập lịch nhóm được đề xuất Giai đoạn 1: Phân lớp các gói điều khiển đến trong khe thời gian τ dựa trên bước sóng đến của chùm. Các thông tin trong gói điều khiển bao gồm thời điểm đến, thời điểm kết thúc và kênh bước sóng đến của chùm tương ứng. Mỗi kênh bước sóng ra duy trì một giá trị LAU T (Lastest Available Unscheduled Time) là thời gian khả dụng sau cùng nhất có thể lập lịch cho các chùm đến. Một gói điều khiển đến trong khe thời gian τ được xem là đủ điều kiện để xét lập lịch nếu thời điểm đến của chùm tương ứng lớn hơn giá trị 11 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 LAU T trên kênh ra của nó. Dựa vào thông tin kênh bước sóng đến, các gói điều khiển (tương ứng các chùm đến) được đưa vào hàng đợi có thể lập lịch cùng nhau. Quá trình lập lịch tiếp tục được chuyển sang Giai đoạn 2. Giai đoạn 2: Lập lịch đồng thời cho các chùm tương ứng với các gói điều khiển trong hàng đợi. Tương tự giải thuật MWIS-OS, danh sách các chùm được chọn lập lịch là các chùm có tổng độ dài lớn nhất. Từ mô hình lập lịch nhóm này, Luận án đề xuất giải thuật lập lịch nhóm như sau. 3.3.2. Giải thuật đề xuất LGS Giải thuật lập lịch nhóm trên đơn kênh LGS đã được công bố trong [CT7]. Xét n gói điều khiển {BHP1 , BHP2 , . . . , BHPn } đến trong khe thời gian τ trên một kênh i, trong đó n là số gói điều khiển đến, tương ứng n chùm cần lập lịch I = {b1 , b2 , . . . , bn }, trong đó bi = (si , ei ) là một bộ hai với si là thời điểm đến của chùm, ei là thời điểm kết thúc (chiều dài của chùm được tính là li = ei − si ); hai chùm bi = (si , ei ) và bj = (sj , ej ) chỉ có thể được lập lịch với nhau nếu thời điểm đến của chúng không chồng lên nhau (tức là (([si , ei ] ∩ [sj , ej ]) = ∅). Giải thuật lập lịch LGS được thể hiện như sau: Algorithm 3.2: LGS (Linear Group Scheduling) Input : I = {b1 , b2 , . . . , bn }; Output: I 0 tập các chùm có tổng chiều dài lớn nhất được lập lịch (I 0 ⊆ I); 1 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm; 2 foreach bj ∈ I do 3 i := j − 1; 4 repeat 5 if (sj > ei ) then 6 index(j) := i và break; 7 else 8 index(j) := 0; 9 10 11 12 13 i := i − 1; until i = 0; C(0) := 0; foreach bj ∈ I do C(j) := max{C(j − 1), lj + C(index(j))}; 21 j := n; cost := C(n); while (j > 0) do if (cost = C(j − 1)) then j := j − 1; else I 0 := I 0 ∪ {bj }; j := index(j); cost := C(j); 22 Lập lịch cho tất cả các chùm trong I 0 ; 14 15 16 17 18 19 20 Độ phức tạp của giải thuật LGS là: O(n × log(n)). 12 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 Tuy nhiên để giảm bớt thời gian thực hiện và độ phức tạp của giải thuật, trong khe thời gian τ chờ lập lịch, mỗi gói điều khiển j đến đều được sắp xếp ngay và tính giá trị index(j) của nó thì thời gian thực hiện của mô hình lập lịch sẽ được giảm xuống và độ phức tạp của giải thuật chỉ còn là O(n). Bên cạnh đó để tận dụng các khoảng trống được tạo ra giữa các chùm đã được lập lịch trên các kênh ra nhằm giảm xác suất mất gói và tăng hiệu quả của giải thuật lập lịch, trên mỗi kênh bước sóng ra bộ lập lịch thay vì chỉ lưu giá trị LAU T , nó sẽ duy trì thời điểm bắt đầu(ski ) và thời điểm kết thúc(eki ) của các chùm i đã được lập lịch trên kênh thứ k đó. Một gói điều khiển đến trong khe thời gian τ được xem là đủ điều kiện để xem w k k w w xét lập lịch cho chùm tương ứng (sw i , ei ) trên kênh đó nếu w = k, si > ei và sj+1 > ei . Cải tiến này được gọi là giải thuật LGS-VF. 3.3.3. Các giải thuật mở rộng đề xuất từ LGS Giải thuật lập lịch nhóm thích nghi trên đơn kênh LAGS, LAGS-VF đã được công bố trong [CT4], [CT5]. Trong mô hình lập lịch nhóm được trình bày trong Mục 3.3.1, khe thời gian lập lịch nhóm τ được ấn định cố định trước và không thay đổi trong suốt quá trình vận hành của mạng. Tuy nhiên, khi tốc độ các chùm đến thay đổi, số gói điều khiển đến trong khe thời gian này cũng sẽ tăng giảm khác nhau. Số lượng các gói điều khiển thực hiện lập lịch đồng thời có một ảnh hưởng nhất định đến hiệu quả lập lịch và thời gian lập lịch. Rõ ràng có một nhu cầu cần thay đổi độ rộng của khe thời gian lập lịch nhóm τ . Hàm điều chỉnh khe thời gian lập lịch nhóm τ chuyển biến theo tốc độ luồng các chùm đến được mô tả như sau: Function AdaptiveTimeslot Input : τmin , τmax , Vavg ; Output: τ, Vavg ; Na 1 Va := ; τ 2 if (Va > Vavg ) then a a ; 3 := − VVavg 4 5 6 7 8 9 10 11 12 else a := Va ; Vavg a τ := τ + ×τstep ; if (τ < 2 × τmin ) then τ := 2 × τmin ; if (τ > τmax ) then τ := τmax ; avg ) Vavg := (Va +V ; 2 return τ, Vavg ; Rõ ràng hàm AdaptiveTimeslot điều chỉnh được khe thời gian lập lịch nhóm τ theo tốc độ đến của các chùm và có thể thấy ngay độ phức tạp của giải thuật này là O(1). Khi bổ sung hàm điều chỉnh khe thời gian lập lịch nhóm(AdaptiveTimeslot) vào sau Dòng 18 của giải thuật lập lịch nhóm LGS hay giải thuật lập lịch nhóm cải tiến LSG-VF, giải thuật 13 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 lập lịch nhóm được đề xuất trở nên thích nghi vì khe thời gian lập lịch nhóm lúc này được điều chỉnh thích nghi chuyển biến theo tốc độ luồng các chùm đến, nên có tên gọi là LAGS(Linear Adaptive Group Scheduling), LAGS-VF(Linear Adaptive Group Scheduling – Void Fill ) và được mô tả như sau: Algorithm 3.3: LAGS (Linear Adaptive Group Scheduling) Input : I = {b1 , b2 , . . . , bn }, τmin , τmax , Vavg ; Output: I 0 tập các chùm có tổng chiều dài lớn nhất được lập lịch(I 0 ⊆ I), τ, Vavg ; 1 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm; 2 foreach bj ∈ I do 3 i := j − 1; 4 repeat 5 if (sj > ei ) then 6 index(j) := i và break; 7 else 8 index(j) := 0; 9 10 11 12 13 14 15 16 17 18 19 20 21 i := i − 1; until i = 0; C(0) := 0; foreach bj ∈ I do C(j) := max{C(j − 1), lj + C(index(j))}; j := n; cost := C(n); while (j > 0) do if (cost = C(j − 1)) then j := j − 1; else I 0 := I 0 ∪ {bj }; j := index(j); cost := C(j); Lập lịch cho tất cả các chùm trong I 0 ; AdaptiveT imeslot(τmin , τmax , Vavg ); 3.4. Mô phỏng và phân tích kết quả Mục này sẽ trình bày chi tiết về cài đặt các giải thuật lập lịch nhóm đã đề xuất LGS, LGS-VF, LAGS-VF và so sánh (về xác suất mất gói tin và độ trễ) với giải thuật lập lịch trực tiếp LAUC-VF và hai giải thuật lập lịch nhóm OBS-GS, MWIS-OS đã được công bố trước đây. Với môi trường mô phỏng được trình bày ở trong Mục 2.4. Mô hình mạng mô phỏng Dumbbell bao gồm 2 nút lõi (C1 và C2 ), trong đó mỗi nút lõi kết nối với 5 nút biên (Ei , i = 1, . . . , 10). Kết quả mô phỏng được thể hiện ở Hình 3.12 đến Hình 3.17 cho thấy giải thuật lập lịch nhóm đề xuất LGS và các cải tiến LGS-VF, LAGS, LAGS-VF có xác suất mất gói tin, độ phức tạp giải thuật thấp hơn so với các giải thuật đã công bố, bên cạnh đó với sự thay đổi khe thời gian τ hợp lý theo tình trạng của các gói điều khiển đến nên tận dụng băng thông lập lịch tốt hơn và giảm được thời gian chờ lập lịch, do đó giảm được độ trễ truyền thông đầu cuối. 14 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 Hình 3.12. So sánh xác suất mất gói tin Hình 3.13. So sánh xác suất mất gói tin giữa LAUC-VF và LGS của OBS-GS, MWIS-OS, LGS và LGS-VF Hình 3.14. So sánh thông lượng của OBS-GS, Hình 3.15. So sánh xác xuất mất gói tin giữa MWIS-OS và LGS-VF LGS-VF và LAGS-VF Hình 3.16. Phân bố độ rộng khe thời gian τ của Hình 3.17. So sánh thời gian chờ trung bình của MWIS-OS và LAGS-VF MWIS-OS và LAGS-VF 3.5. Tiểu kết Chương 3 Chương này của Luận án đã trình bày, phân tích, đánh giá các giải thuật lập lịch nhóm trên đơn kênh đã được công bố. Qua đó đưa ra được những ưu điểm và một số tồn tại của các giải thuật lập lịch này. Trên cơ sở đó Luận án đề xuất giải thuật lập lịch nhóm LGS và các cải tiến LGS-VF và LAGS-VF có độ phức tạp của các giải thuật 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 đó. Bên cạnh đó giải thuật đề xuất tận dụng được các khoảng trống tạo ra giữa các chùm đã lập lịch trước đó để lập lịch cho chùm đến, vì vậy giảm xác suất mất gói tin và điều khiển tắc nghẽn tốt hơn. Ngoài ra khe thời gian chờ lập lịch thích nghi theo tốc độ đến các gói điều khiển vì vậy giảm được độ trễ đầu cuối. Thông qua kết quả mô phỏng đã chỉ ra rằng giải thuật LGS-VF và giải thuật lập lịch nhóm thích nghi LAGS-VF hiệu quả hơn nhiều (dựa trên xác suất mất gói tin) so với giải thuật lập lịch trực tiếp LAUC-VF và hai giải thuật lập lịch nhóm OBS-GS, MWIS-OS đã được công bố trước đây. Hơn nữa, giải thuật LAGS-VF còn cải thiện đáng kể thời gian lập lịch 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 mạng OBS khác và các hoạt động truyền thông trong mạng. 15 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 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 4.1. Giới thiệu Trường hợp nút lõi mạng 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 một kênh ra bất kỳ với hỗ trợ của bộ chuyển đổi bước sóng. Loại lập lịch nhóm với hỗ trợ của các bộ chuyển đổi bước sóng được gọi là lập lịch nhóm trên đa kênh 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ố 4.2.1. Nhóm các giải thuật lập lịch heuristic Nhóm giải thuật lập lịch heuristic được đề xuất bởi Kaheel và cộng sự bao gồm các giải thuật SSF (Smallest Start-time First), LIF (Largest Interval First), SLV (Smallest-Last Vertex ) và MCF (Maximal Cliques First). 4.2.1.1. Giải thuật SSF 4.2.1.2. Giải thuật LIF 4.2.1.3. Giải thuật SLV 4.2.1.4. Giải thuật MCF 4.2.2. Nhóm các giải thuật lập lịch tối ưu Các giải thuật heuristic được trình bày ở trên rõ ràng không đạt được kết quả lập lịch tối ưu. Một hướng tiếp cận khác của tác giả Figueiredo và cộng sự đã đề xuất hai giải thuật GreedyOPT và BATCHOPT. Ý tưởng của hai giải thuật này chuyển từ bài toán S-NIM thành S-IM bằng cách gỡ hết các chùm đã lập lịch trước đó và lập lịch lại chúng đồng thời với các chùm mới đến, với hi vọng sẽ lập lịch được kết quả tốt hơn. 4.2.2.1. Giải thuật GreedyOPT 4.2.2.2. Giải thuật BATCHOPT 4.3. Các giải thuật lập lịch nhóm đề xuất trên đa kênh Như trình bày ở trên các giải thuật lập lịch nhóm theo hướng heuristic có độ phức tạp giải thuật thấp do chỉ dựa trên cách sắp xếp các chùm trước khi thực hiện lập lịch tuần tự, nhưng chúng chưa đưa ra được tiêu chí chọn tập các chùm tối ưu trong lập lịch. Ngược lại đối với các giải thuật theo hướng tiếp cận tối ưu lập lịch để đạt được kết quả lập lịch tối ưu, giải thuật GreedyOPT, BATCHOPT phải chịu một độ phức tạp lớn về mặt tính toán, hệ thống phải có những thay đổi trong giao thức trong đặt trước lại tài nguyên, số gói điều khiển tăng lên, các nút mạng OBS phải thực hiện nhiều xử lý hơn và tranh chấp tài nguyên do đó sẽ tăng thêm. Để khắc phục những tồn tại này, Luận án đề xuất một số giải thuật lập lịch nhóm trên đa kênh ra theo 2 hướng tiếp cận: heuristic và tối ưu kết quả lập lịch. Các đề xuất này cũng đã được công bố trong [CT1], [CT3] và [CT6]. Sau đây là phần mô tả chi tiết về các giải thuật này. 16 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 4.3.1. Giải thuật lập lịch nhóm tối ưu OPT-GS Xét tập các n gói điều khiển {BHP1 , BHP2 , . . . , BHPn } đến trong khe thời gian τ , yêu cầu lập lịch cho n chùm tương ứng của nó I = {b1 , b2 , . . . , bn }. Vấn đề là tìm tập các chùm I 0 ⊆ I có thể lập lịch cùng nhau trên m kênh ra có tổng độ dài các chùm được lập lịch là lớn nhất. Để giải quyết bài toán này, Luận án mô hình hoá bài toán lập lịch nhóm trên đa kênh sang bài toán tìm tập các đường đi trên đơn đồ thị khoảng có hướng có trọng số. Giải thuật OPT-GS được mô tả chi tiết như sau: Algorithm 4.4: OPT-GS (Optimal Group Scheduling ) Input : I = {b1 , b2 , . . . , bn }, W = {1, 2, . . . , m}; Output: I 0 tập các chùm được lập lịch trên m kênh ra; 1 Sắp xếp không giảm các kênh theo giá trị LAU T ; 2 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm và tập A là tập các chùm sau khi đã sắp xếp. 3 V := ∅; E := ∅; 4 foreach ai ∈ A do 5 Tạo đỉnh i; V := V ∪ {i}; 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 foreach i, j ∈ V sao cho i < j do if (ei > sj ) ∧ (@k(∀k ∈ (i + 1, j − 1)|((ei > sk ) ∧ (ek > sj ))) then Tạo cung (i, j) đi từ i đến j; E := E ∪ {(i, j)}; Trọng số của đỉnh i là li := ei − si ; foreach w ∈ W do Dw = ∅; foreach i ∈ V sao cho ((si > LAU Tw ) ∧ ((j, i) ∈ / E) ∧ (sj > LAU Tw )) do w Tìm tất cả các đường đi di xuất phát từ đỉnh i trên kênh w có dạng {r1 , r2 , . . . , rl } trong đó r1 = i, (ri , ri+1 ) ∈ E, với ∀i = 1, 2, . . . , l − 1 và (rl , rk ) ∈ / E với ∀k > l; Dw := Dw ∪ {dw i }; foreach j ∈ |D1 | do pj := d1j ; P := P ∪ {pj }; Q := ∅; h := 0; foreach w ∈ {2, 3, . . . , m} do foreach i ∈ |P | do foreach dw i ∈ Dw do h := h + 1; qh := pi ∪ {dw j } r {pi }; Q := Q ∪ {qh }; P := Q; h := 0; Q := ∅; 27 pmax := ∅; Lmax := 0; foreach pi ∈ P do Tính tổng trọng số các đỉnh trong pi ký hiệu là Li ; if (Li > Lmax ) then Lmax := Li ; pmax := pi ; 28 Lập lịch cho các chùm tương ứng các đỉnh trong pmax ; 23 24 25 26 17 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 Độ phức tạp giải thuật OPT-GS là: O(|P | × |D|). 4.3.2. Giải thuật lập lịch nhóm heuristic LGS-MC Giải thuật lập lịch nhóm trên đa kênh LGS-MC đã được công bố trong [CT6]. Giải thuật LGS-MC (Linear Group Scheduling for Multi Channel ) là một mở rộng của giải thuật lập lịch nhóm trên đơn kênh LGS. Tư tưởng của giải thuật LGS-MC là tối ưu lập lịch trên mỗi kênh. Giải thuật LGS-MC được mô tả chi tiết như sau: Algorithm 4.5: LGS-MC(Linear Group Scheduling for Multi Channel ) Input : I = {b1 , b2 , . . . , bn }, W = 1, 2, . . . , m; Output: I 0 tập các chùm có tổng chiều dài các chùm được lập lịch trên mỗi kênh là lớn nhất; 0 1 I := ∅; 2 Sắp xếp không giảm các kênh theo giá trị LAU T ; 3 while (w ≤ m) ∧ (I 6= ∅) do 4 foreach bi ∈ I do 5 if (si < LAU Tw ) then 6 I := I r {bi }; 7 8 9 10 11 12 13 14 15 16 17 18 19 Sắp xếp không giảm tập I theo thời điểm kết thúc của mỗi chùm; foreach bj ∈ I do k := j − 1; repeat if (sj > ek ) then index(j) := k và break; else index(j) := 0; k := k − 1; until k = 0; C(0) := 0; foreach bj ∈ I do C(j) := max{C(j − 1), li + C(index(j))}; 25 j := n; cost := C(n); while (j > 0) do if (cost = C(j − 1)) then j := j − 1; else I 0 := I 0 ∪ {bj }; I := I r {bj }; j := index(j); cost := C(j); 26 w := w + 1; 20 21 22 23 24 Độ phức tạp của giải thuật LGS-MC là: O(n × log(n)). 4.3.3. Giải thuật lập lịch nhóm heuristic MWC-GS Luận án mô hình hoá khả năng lập lịch của các chùm đến trên các kênh ra bằng một đồ thị khoảng G = (V, E), trong đó mỗi đỉnh bki ∈ V biểu diễn một khả năng lập lịch của chùm bi trên kênh k và mỗi cạnh {bki , bhj } ∈ E tương ứng với một trong 2 trường hợp: 2 chùm bi và bj được lập lịch trên cùng một kênh (k = h) mà có thời gian không chồng lấp 18