MỘT HƯỚNG TIẾP CẬN LẬP LỊCH NHÓM TỐI ƯU TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 7 liệu trên toàn mạng. Hiện đã có một số giải thuật lập lịch nhóm được đề xuất 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) [7]; LGS-MC (Linear Group Scheduling for Multi Channel) [10], MWC-GS (Maximum Weight Clique - Group Scheduling) [17] và hướng tiếp cận tối ưu lập lịch 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 trên máy đồng nhất bao gồm GreedyOPT (Gready Optimization) [4], BATCHOPT (Batch Optimization) [5] và OPT-GS (Optimal Group Scheduling) [13]. 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 đạt được kết quả lập lịch tối ưu; trong khi các giải thuật theo hướng tiếp cận tối ưu, như GreedyOPT, BATCHOPT và OPT-GS 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. Ngoài ra việc gỡ tất cả các chùm đã được lập lịch trên các kênh là không thực tế ở trên mạng thật. Trong nghiên cứu này chúng tôi đề xuất một giải thuật lập lịch nhóm tối ưu kết quả lập lịch và giảm được độ phức tạp giải thuật. Cấu trúc tiếp theo của bài viết như sau: Phần II trình bày các nghiên cứu liên quan đến

các công bố, Phần III mô tả giải thuật lập lịch nhóm đề xuất; Phần IV mô phỏng đánh giá giải thuật lập lịch nhóm đề xuất và Phần V là phần kết luận. 2 Một số nghiên cứu liên quan Đã có một số giải thuật lập lịch được công bố nhằm giải quyết bài toán lập lịch nhóm trên đa kênh theo 2 hướng tiếp cận: tối ưu hoá lập lịch [4], [5] [13] hoặc sử dụng giải pháp heuristic [7] [10] [17] để giảm độ phức tạp của giải thuật. Nhóm giải thuật lập lịch heuristic được đề xuất trong [7] [10] [17] bao gồm các giải thuật SSF, LIF, SLV, MCF, LGS-MC và MWC-GS. Nhóm giải thuật lập lịch nhóm theo hướng tiếp cận tối ưu kết quả lập lịch được các tác giả trong [4], [5] đề xuất gồm 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. Bên cạnh đó các tác giả trong [13] đề xuất giải thuật lập lịch nhóm tối ưu OPT_GS nhằm tìm ra tập các chùm có độ dài lớn nhất để lập lịch trên các kênh. Trong [7] tác giả đề xuất giải thuật SSF với 𝑛 gói điều khiển đến trong khe thời gian 𝜏 yêu cầu lập lịch cho n chùm theo sau tương ứng, giải thuật SSF tiến hành sắp xếp thứ tự không giảm theo thời điểm đến của các chùm. Sau đó giải thuật LAUC-VF (Latest Available Unused