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

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 10 Từ các giải thuật đã được công bố của các tác giả cho thấy các giải thuật lập lịch nhóm trên đa kênh theo hướng tiếp cận heuristic nhằm giảm độ phức tạp tính toán tuy nhiên chưa đưa ra tiêu chí chọn lập lịch cho các chùm đến mà chỉ dựa vào thứ tự sắp xếp. Với các giải thuật lập lịch nhóm trên đa kênh theo hướng tiếp cận tối ưu lấy ý tưởng từ bài toán lập lịch công việc trên máy đồng nhất, nhằm đạt được kết quả lập lịch tối ưu và có độ phức tạp thấp. Để thực hiện được việc này 2 giải thuật thực hiện gỡ hết tất cả các chùm đã được lập lịch trên các kênh và xem xét lập lịch đồng thời với các chùm đến. Việc làm này sẽ làm tăng số lượng gói điều khiển phải gửi lại, yêu cầu hệ thống phải có sự thay đổi về mặt giao thức. Bên cạnh đó giải thuật OPT_GS có độ phức tạp lớn nên không phù hợp để áp dụng vào trong mạng chuyển mạch chùm quang. 3 Giải thuật lập lịch được đề xuất MF_GS (Maximum Flow Group Scheduling) Xét tập n gói điều khiển {𝐵𝐻𝑃1, 𝐵𝐻𝑃2, . . . , 𝐵𝐻𝑃𝑛} đến trong khe thời gian 𝜏, yêu cầu lập lịch cho n chùm tương ứng của nó 𝐼 = {𝑏1, 𝑏2, . . . , 𝑏𝑛}, mỗi 𝑏𝑖(𝑖 = 1, 2, . . . , 𝑛) được mô tả bởi cặp (𝑠𝑖 , 𝑒𝑖) trong đó 𝑠𝑖 là thời điểm đến và 𝑒𝑖 thời điểm kết thúc chùm trên tập 𝑚 kênh ra tại một cổng ra (𝑊 = 1, 2, . . . , 𝑚), với 𝑚 là hằng số. Hai chùm 𝑏𝑖 và 𝑏𝑗 được cho là có thể lập lịch cùng nhau trên kênh thứ 𝑘 (𝑘 = 1, 2, . . . , 𝑚) nếu thời điểm đến của chùm lớn hơn giá trị 𝐿𝐴𝑈𝑇 trên kênh đó ( 𝑠𝑖 > 𝐿𝐴𝑈𝑇𝑘 và 𝑠𝑗 > 𝐿𝐴𝑈𝑇𝑘 ) và thời gian đến của chúng không chồng lấp

nhau([𝑠𝑖 , 𝑒𝑖 ] ∩ [𝑠𝑗 , 𝑒𝑗] = ∅). Vấn đề là tìm tập các chùm 𝐼0 ⊆ 𝐼 có thể lập lịch cùng nhau trên 𝑚 kênh ra có tổng độ dài các chùm được lập lịch là lớn nhất Mô hình đề xuất thực hiện như mô tả ở Hình 1: Khi các gói điều khiển đến trong mỗi khe thời gian sẽ được đưa vào một hàng đợi lập lịch cùng nhau. Sau khi hết thời gian chờ, lúc này thực hiện gọi giải thuật lập lịch để lập lịch cho tất cả các chùm tương ứng các gói điều khiển trong hàng trên tất cả các kênh ra. Ví dụ: Xét một tập có 6 gói điều khiển {𝐵𝐻𝑃1, 𝐵𝐻𝑃2, 𝐵𝐻𝑃3, 𝐵𝐻𝑃4, 𝐵𝐻𝑃5, 𝐵𝐻𝑃6} đến trong khe thời gian  , như Hình 1. (a), yêu cầu lập lịch cho 6 chùm tương ứng 𝐼 = {𝑏1, 𝑏2, 𝑏3, 𝑏4, 𝑏5, 𝑏6}, độ dài của các chùm lần lượt là: 𝑙1 = 3, 𝑙2 = 4, 𝑙3 = 3, 𝑙4 = 5, 𝑙5 = 6, 𝑙6 = 4 trên hai kênh dữ liệu ra với giá trị 𝐿𝐴𝑈𝑇1 và 𝐿𝐴𝑈𝑇2 tương ứng.